프로그래머스 - 괄호 회전하기

✨ Lv. 2 - 괄호 회전하기

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/76502

문제 설명

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

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

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

제한사항

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

풀이 코드 + 설명

처음 떠올린 풀이법은 stack을 활용하는 것입니다. 우선 s의 길이만큼 반복하여 1칸씩 회전시킨 문자열을 순회하며 다음을 반복합니다.

• (, {, [ 일 경우에는 stack에 이를 push 합니다.
• ), }, ] 일 경우에는 stack의 가장 위에 있는 괄호와 짝이 맞는지를 판단합니다.
• 짝이 맞는 경우, stack에서 pop한 이후, 계속 진행합니다.
• 짝이 맞지 않는 경우, break 후, 다음 문자열에 대해 위 내용을 반복합니다.

최종적으로 매 경우마다 끝까지 순회를 완료하였으며, stack에 남아있는 괄호가 없는 경우에는 올바른 괄호 문자열이라고 할 수 있습니다. 반대로 stack에 괄호가 남아있거나, 끝까지 순회하지 못하였을 경우에는 올바르지 않은 괄호 문자열이 됩니다.

이를 바탕으로 작성한 코드는 아래와 같습니다.

function solution(s) {
    let result = 0;
    
    for(let i = 0; i < s.length; i++) {
        s = s.slice(1) + s[0];
        let stack = [];
        let current = true;
        for(let j = 0; j < s.length; j++) {
            if(s[j] === '(' || s[j] === '{' || s[j] === '[') stack.push(s[j]);
            else if(s[j] === ')' && stack.at(-1) === '(') stack.pop();
            else if(s[j] === '}' && stack.at(-1) === '{') stack.pop();
            else if(s[j] === ']' && stack.at(-1) === '[') stack.pop();
            else {
                current = false;
                break;
            }
        }
            if(stack.length === 0 && current) result++;
    }
    
    return result;
}

stack 대신에 정규표현식을 활용하여 풀이할 수도 있습니다. (), [], {} 와 같이 올바른 최소한의 괄호쌍을 빈 문자열로 replace 하여 문자열이 빈 문자열이 될 수 있는 경우가 바로 올바른 괄호 문자열이 됩니다.

function solution(s) {
    let result = 0;
    
    for(let i = 0; i < s.length; i++) {
        s = s.slice(1) + s[0];
        let current = s;
        while(true) {
            const curLength = current.length;
            current = current.replace(/\(\)|\[\]|\{\}/g, '');
            if(curLength === current.length) break;
        }
        if(current === '') result++;
    }
    
    return result;
}