[JavaScript] 프로그래머스 코딩테스트 레벨 2 : 괄호 회전하기

📌  문제

다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다.

• (), [], {} 는 모두 올바른 괄호 문자열입니다.
• 만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다. 예를 들어, [] 가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다.
• 만약 A, B가 올바른 괄호 문자열이라면, AB 도 올바른 괄호 문자열입니다. 예를 들어, {} 와 ([]) 가 올바른 괄호 문자열이므로, {}([]) 도 올바른 괄호 문자열입니다.

대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다. 이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요.

📌  제한사항

• s의 길이는 1 이상 1,000 이하입니다.

📌  입출력 예

---

📌  풀이

• 괄호와 같이 어떤 짝을 맞춰야 하는 문제는 주로 스택으로 해결할 수 있다.
  • 단 괄호가 소괄호 한 종류가 아니라 중괄호, 대괄호까지 있다.
  • OR문을 써서 해도 되지만 그러면 뭔가 복잡한 감이 있어서 객체로 짝을 찾기로 했다.
  • pairs라는 객체를 만들어 열린 괄호와 닫힌 괄호를 키와 값으로 짝지어준다.
• 올바른 괄호 문자열이 되게 하는 x의 개수를 카운트할 변수 answer는 0으로 초기화한다.
• 주어진 문자열 s를 회전 시키게 될 때 문자열의 형태가 변하게 된다.
  • for문으로 s를 0부터 s.length-1만큼 순회한다. 즉 x의 범위만큼 순회한다.
  • 이 때 i만큼 잘라내고, 0부터 i만큼을 자른 문자열을 붙인다.
  • 예컨대 [)(]라고 할 때 s.slice(0) + s.slice(0, 0)을 하면 처음부터 끝까지 + 0을 더해 문자열이 변하지 않는다.
  • 반면 s.slice(1) + s.slice(0, 1)을 하면 인덱스 1부터 끝까지 + 인덱스 0을 더해 문자열의 첫 번째 문자가 맨 뒤에 붙게 된다.
  • 이런 식으로 rotated를 바꿔 만들어낸다.
•  isCorrect라는 함수는 위에서 만든 rotated를 매개변수로, 문자 하나씩을 순회한다.
  • 이 때 현재 문자가 열린 괄호라면 stack에 push한다.
  • 닫힌 괄호라면 경우가 2가지로 나뉜다.
    • 스택에 아무 것도 들어있지 않은 상태에서 닫힌 괄호부터 들어가면 이미 망한 괄호이기 때문에 false를 반환한다.
    • 무언가 들어 있는 상태라면 스택의 가장 오른쪽에 있는 요소를 pop으로 가져온 후, pop으로 가져온 이 괄호의 짝이 현재 문자인지 체크한다. 만약 pop으로 가져온 괄호의 짝이 현재 문자라면 pop 된다.
  • 이렇게 매개변수로 들어온 문자열을 전부 순회했을 때 stack이 비게 되면 전부 짝이 맞으므로 true일 때 answer++를 해주면 x의 개수를 카운트 할 수 있다.

function solution(s) {
    let answer = 0;
    const stack = [];

    const isCorrect = (str) => {
        const pairs = { '(': ')', '[': ']', '{': '}' };
        for (let char of str) {
            if (char === '[' || char === '(' || char === '{') {
                stack.push(char);
            } else {
                if (stack.length === 0) {
                    return false;
                } else {
                    const top = stack.pop();
                    if (pairs[top] !== char) {
                        return false;
                    }
                }
            }
        }
        return stack.length === 0;
    };

    for (let i = 0; i < s.length; i++) {
        const rotated = s.slice(i) + s.slice(0, i);
        if (isCorrect(rotated)) {
            answer++;
        }
    }

    return answer;
}

 

이렇게 짝 맞추는 문제는 스택으로 풀어야 한다는 생각은 들었는데 어떻게 접근해야 할지 좀 고민이 됐다.

특히 괄호가 많다 보니 이걸 객체로 짝지을 생각을 못 했는데 앞으로 객체로도 많이 접근해봐야겠다.