[프로그래머스] 올바른 괄호 (Lv. 2, JavaScript)

📝 문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/12909

프로그래머스

목표: 괄호로 이루어진 문자열이 주어졌을 때 괄호가 짝지어서 닫힌 형태로만 존재해야 한다. 이를 확인해 true 혹은 false 를 반환하는 것이 목표

핵심 조건:

• 괄호가 있다면 무조건 짝지어서 닫힌 형태여야 한다. () 예를들어 ()() 혹은 (()) 와 같이 되어야 하며, ((()) 나 )()() 는 조건이 부합하지 않는다.
• 문자열 s의 길이는 100,000 이하의 자연수
• 문자열 s는 ‘(’ 또는 ‘)’ 로만 이루어져 있다.

---

풀이 과정 (나만의 풀이 전략)

문자열 s에서 순서대로 볼 때 ‘(’ 가 1회 이상 연속으로 나온다면 이후에는 ‘)’가 ‘(’의 개수와 동일하게 연속으로 등장해야 괄호의 규칙에 맞게 된다.

예를들면 ((( 3개 라면 동일하게 ))) 3개여야 하고, (( ) (( ))) 이 경우에도 ‘(’가 4회 ‘)’ 역시 4개로 조건을 충족한다.

다만 )((), ())( , ())(()의 경우 개수가 동일하나 조건을 충족하지 못하는데,

이는 아래 예외 케이스의 경우에 조건을 충족하지 않는다.

1. ) 가 ( 보다 먼저 나오는 경우에는 무조건 false
2. ( 로 끝나는 경우 무조건 false
3. ( 가 나온 횟수보다 ) 가 바로 뒤이어 더 많이 나올 경우에도 false

위 케이스를 제외하면, 두 괄호의 개수가 동일하면 true를 반환한다.

🛠️ 트러블슈팅

1차 코드

function solution(s){
    var answer = true;
    
    // 문자열 s를 배열로 변환
    let arr = s.split("");
    
    // 두 괄호의 개수가 다르다면
    let leftCount = arr.filter((s) => s === '(').length;
    let rightCount = arr.filter((s) => s === ')').length;
    
    if (leftCount !== rightCount) {
        answer = false;
    }
    
    
    // case 1. ( 가 먼저 나올 경우 무조건 올바르지 않은 경우
    // case 2. ( 로 끝나는 경우 무조건 올바르지 않은 경우
    if (arr[0] === ')' || arr[arr.length - 1] === '(')  {
        return false;
    }

    leftCount = 0;
    rightCount = 0;
    
    // O(N)
    while (arr.length > 0) {
        char = arr.shift();
        if (char === '(') {
		        // case 3. (를 추출했을 때 )가 나온 개수 보다 작다면
            if (leftCount < rightCount) {
                return false;
            }
            leftCount++;
            continue;
        }
        
        if (char === ')') {
            rightCount++;
        }
    }
    
    

    

    return answer;
}

1차로 구현한 코드에서 정확성 테스트 케이스는 모두 통과했으나, 효율성 테스트에서 시간 초과로 인해 통과하지 못했다.

 

기존 코드의 시간 복잡도는 문자열의 길이만큼 반복문을 돌도록 설정했으므로, 최악의 경우 O(N)이다.

더 시간복잡도를 줄일 수 있는 방법이 있을까? 해서 두 번째로 도입한 방법은 정규표현식을 활용하여 ‘(’ 묶음과 ‘)’ 묶음으로 배열을 재구성한다. 이러면 [’(((’, ‘))’, ‘(’, ‘)))’] 이러한 형태로 구성된다.

이런 다음 배열을 순회하면서 문자열의 길이에 따라 Case 3를 검증하면 어떨까? 했다.

다만 특정 테스트 케이스를 통과하지 못했고 결론적으로 오히려 성능면에서 좋지 않다는 점인데, match 메서드의 시간 복잡도가 O(N)이고 내부 연산 오버헤드 역시 발생 가능하다는 문제가 있었다.

 

결국 다시 처음 1차 코드 (문자열 순회)에서 문제점을 찾을 수 있었는데, 기본적인 O(N) 시간복잡도는 유지하되, shift() 메서드를 사용하는 것이 문제였다. 배열의 메서드를 사용하는 것이 생각보다 시간 복잡도 측면에서 손실이 있었고 이를 배열을 순회할때마다 하니 시간이 오래걸렸던게 문제였다… 생각보다 너무 간단한 문제에 끙끙대고 있었다.

---

💻 코드 (Code)

function solution(s){
    var answer = true;
    
    // 문자열 s를 배열로 변환
    let arr = s.split("");
    
    // case 1. ( 가 먼저 나올 경우 무조건 올바르지 않은 경우
    // case 2. ( 로 끝나는 경우 무조건 올바르지 않은 경우
    if (arr[0] === ')' || arr[arr.length - 1] === '(')  {
        return false;
    }
    
    // 두 괄호의 개수가 다르다면
    let leftCount = arr.filter((s) => s === '(').length;
    let rightCount = arr.filter((s) => s === ')').length;
    
    if (leftCount !== rightCount) {
        return false;
    }
    
    // O(N)
    leftCount = 0;
    rightCount = 0;

    for (let index = 0; index < arr.length; index++) {
        if (arr[index] === '(') {
            // case 3. (를 추출했을 때 )가 나온 개수 보다 작다면
            if (leftCount < rightCount) {
                return false;
            }
            leftCount++;
        } else if (arr[index] === ')') {
            rightCount++;
        }
    }

    
    
    return answer;
}

function solution(s){
    var answer = true;
    
    // case 1. ( 가 먼저 나올 경우 무조건 올바르지 않은 경우
    // case 2. ( 로 끝나는 경우 무조건 올바르지 않은 경우
    if (s[0] === ')' || s[s.length - 1] === '(')  {
        return false;
    }
    
    const arr = s.match(/\\)+|\\(+/g)
	
    leftCount = 0;
    
    // case 3 점검
    for (word of arr) {
        if (word[0] === '(') {
            leftCount += word.length;
        } else if (word[0] === ')') {
            leftCount -= word.length;
            if (leftCount < 0) {
                return false;
            }
        }
    }
    
    
    return leftCount === 0;
}

최적화된 코드

function solution(s){
    var answer = true;
    
    // case 1. ( 가 먼저 나올 경우 무조건 올바르지 않은 경우
    // case 2. ( 로 끝나는 경우 무조건 올바르지 않은 경우
    if (s[0] === ')' || s[s.length - 1] === '(')  {
        return false;
    }
    
    // O(N)
    let leftCount = 0;
    let rightCount = 0;

    for (let index = 0; index < s.length; index++) {
        if (s[index] === '(') {
            leftCount++;
        } else if (s[index] === ')') {
            rightCount++;
            // case 3. (를 추출했을 때 )가 나온 개수 보다 작다면
            if (leftCount < rightCount) {
                return false;
            }
        }
    }

    
    
    return leftCount === rightCount;
}

문자열을 배열로 split을 통해 변환할 필요가 없다. 따라서 문자열을 그대로 사용한다.

for문 이전에 filter을 통해 불필요하게 두 괄호의 개수를 비교할 필요 없이 for문에서 case 3를 걸러낸다면 마지막에 최종 return 직전에 leftCount와 rightCount를 비교하면 되므로, 더 간단하게 작성 가능하다.

---

❓ 꼬리 질문 및 복습 (Self-Q&A)

복습 (추가 학습)

본 문제가 스택&큐 알고리즘 관련 문제라는 점을 생각한다면 leftCount와 rightCount를 별도로 두는게 아니라 스택의 성질을 활용하여 leftCount만 두고도 해결이 가능하다.

‘(’가 나왔을 때 스택의 push처럼 count를 1 증가 시키고 ‘)’가 나온다면 pop 처럼 count를 1 감소시키는 방식으로 진행하고, 스택이 비어있는 상태에서 pop을 시도하려하면 문제가 된다고 보면, count가 0일 때 ‘)’를 만나 감소시키려 한다면 괄호의 규칙에 어긋난다고 볼 수도 있다.

---

💬 마무리하며

스택의 특징을 잘 알고 있다면 쉽게 해결할 수 있는 문제였기에 생각보다 오랜 시간을 투자해서 많이 아쉬움이 남습니다.