문제 10) 괄호 회전하기

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의 개수를 반환하는 solution() 함수를 완성하시오.

 

제약 조건

• s의 길이는 1 이상 1,000 이하

입출력의 예

s	result
"[ ] ( ) { }"	3
"} ] ( ) [ {"	2

---

아이디어

이전 괄호 문제와 동일하게 괄호의 짝을 맞춰야 하므로 스택을 이용해서 풀 수 있다는 것을 생각해야함. 여기서 가장 핵심은 닫힌 괄호를 처음 보는 순간 가장 마지막에 찾았던 같은 모양의 열린 괄호를 찾을 수 있어야 함.. 그러나 이 과정을 생각하지 못하고, 3개의 괄호를 구분하지 못하는 코드를 작성해 "[)(]" 테스트 케이스에 대해 정확한 답이 나오지 않았음.

private static int solution(String s){
        int count = 0;

        // String 회전용 스택
        ArrayDeque<Character> st1 = new ArrayDeque<>();
        // 올바른 괄호 확인용 스택
        ArrayDeque<Character> st2 = new ArrayDeque<>();

        char[] a = s.toCharArray();
        for(char c : a)
            st1.offerLast(c);

        for(int i=0; i<s.length(); i++){
            for(char c : st1){
                if(c == '(' || c == '{' || c == '['){
                    st2.offerLast(c);
                }
                else {
                    if(st2.isEmpty() || st2.pop() == c){
                        count++;
                        break;
                    }
                }
            }
            st1.offerLast(st1.pollFirst());
        }

        return s.length() - count;
    }

---

정답 코드

우선 왼쪽으로 1번 회전 한다는 점을 따로 스택이나 복잡하게 구현하지 않고, 원본 문자열을 그대로 이어 붙여 반복하게 만든 것이 인상적이었다. 해시맵을 만들어 각 괄호의 짝을 정하고, 해당 닫힌 괄호가 스택에 없다면 올바른 괄호 문자열이 아니므로 continue.

해시맵을 조금 더 잘 다룰 수 있도록 해야겠다.

private static int solution(String s){
        HashMap<Character, Character> map = new HashMap<>();
        map.put(')', '(');
        map.put('}', '{');
        map.put(']', '[');

        int n = s.length();
        s += s; // 원본 문자열 뒤에 원본 문자열을 이어 붙여 2번 나오도록 만들어줌
        int answer = 0;

        A: for(int i=0; i<n; i++){
            ArrayDeque<Character> stack = new ArrayDeque<>();

            for(int j=i; j<i+n; j++){
                char c = s.charAt(j);
                if(!map.containsKey(c))
                    stack.push(c);
                else{
                    if(stack.isEmpty() || !stack.pop().equals(map.get(c)))
                        continue A;
                }
            }
            if(stack.isEmpty())
                answer++;
        }
        return answer;
    }