[프로그래머스] - 괄호 회전하기 # Stack

문제 링크

1. 문제 설명

 대괄호, 중괄호, 소괄호로 이루어진 문자열 s가 매개변수로 주어질 때, s를 왼쪽으로 x칸만큼 회전시켰을 때, s가 올바른 문자열이 되도록 하는 x의 개수를 반환하라. 올바른 괄호 문자열이란 (), {}, [], {()}, {}[()], ... 와 같이 여는 괄호 뒤에 반드시 닫는 괄호가 오는 형태를 말한다. 

 

2.  제한 사항

• 0 <= x < s.len()
• 1 <= s.len() <= 1,000

 

3. 입출력 예

 

---

 

4. 첫 번째 풀이 - Python

 스택의 LIFO 특성을 활용한다. 여는 괄호가 나오면 스택에 넣고, 그에 맞는 닫는 괄호가 나오면 스택에서 빼 줄 것이다.

먼저, stack에 빈 리스트를 할당하고, opens 리스트에 {, (, [를 담아준다. closes에는 여는 괄호를 키로 갖고, 여는 괄호에 매칭되는 닫는 괄호를 값으로 갖는 딕셔너리를 할당한다. 

 

 그 후 s를 순회하면서 현재 괄호가 여는 괄호인지부터 판단한다. 닫는 괄호라면 스택의 맨 마지막 들어간 괄호가 그 짝이어야 한다. 올바른 괄호 문자열의 형태를 자세히 보면 닫는 괄호에 대응되는 열린 괄호가 열린 괄호들 중에 맨 마지막에 있기 때문이다. 두 경우 모두에 해당하지 않는다면 여는 괄호로 시작하지 않은 상태에서 닫는 괄호가 나온 것이므로 올바른 괄호 문자열이 아니다.

 

 모든 연산이 끝났을 때는 stack이 비어있어야 하므로 len(stack) == 0 을 반환한다. 스택에 요소가 남아있다면 False, 정상적인 상황이라면 True가 반환될 것이다.

 

 위 과정을 문자열  s의 문자 하나씩 왼쪽으로 이동시키면서 True가 반환될 때마다 answer에 + 1 해준다. deque의 rotate() 메소드를 사용하면 문자열을 쉽게 한칸씩 왼쪽으로 옮길 수 있다. s에 대한 순회가 끝났을 때 결과적으로 더해진 answer를 반환한다. 

from collections import deque

def is_correct(s):
    stack = []
    opens = ["{", "(", "["]
    closes = {"{": "}", "(": ")", "[": "]"}
    
    for i in s:
        if i in opens:
            stack.append(i)
        elif stack and closes[stack[-1]] == i:
            stack.pop()
        else:
            return False
    return len(stack) == 0

def solution(s):
    answer = 0
    s = deque(s)
    for i in range(len(s)):
        if is_correct(s):
            answer += 1
        s.rotate()
        
    return answer

 

 

5. 두 번째 풀이 - Java

 아직 자바 컴파일 에러가 난다.. ^_^ 스택에는 괄호 문자열을 하나씩 자른 괄호 하나가 들어가기 때문에 Character 배열로 만들어줘야하는 것을 놓쳤다.

import java.util.*;

class Solution {
    public boolean isCorrect(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            switch (c) {
                case '(': case '{': case '[': // fall-through
                    stack.push(c);
                    break;
                case ')':
                    if (stack.isEmpty() || stack.pop() != '(') return false;
                    break;
                case '}':
                    if (stack.isEmpty() || stack.pop() != '{') return false;
                    break;
                case ']':
                    if (stack.isEmpty() || stack.pop() != '[') return false;
                    break;
            }
        }
        return stack.isEmpty();
    }
    public int solution(String s) {
        int answer = 0;
        int length = s.length();
        StringBuilder sb = new StringBuilder(s); // 가변 문자열로 변환
        
        for (int i = 0; i < length; i++) {
            if (isCorrect(sb.toString())) {
                answer++;
            }
            sb.append(sb.charAt(0));
            sb.deleteCharAt(0);
        }
        
        return answer;
    }
}

 

 

6. 개념 정리

 파이썬은 여러모로 참 편리하다.. 

• java swith문에서 case '(': case '{': case '[': 이런 식으로 fall-through 방식으로 세 가지 조건을 연속으로 쓸 수 있는데, java12부터는 '(', '{', '[' -> stack.push(c); 요렇게 더 편리하게 쓸 수 있다고 한다.
• String.charAt(i) 보다 문자열.toCharArray()로 문자배열로 만들어서 사용하는 것이 더 효율적이라고 한다.