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

문제 설명

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

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

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

---

제한사항

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

---

입출력 예

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

---

입출력 예 설명

입출력 예 #1

• 다음 표는 "[](){}" 를 회전시킨 모습을 나타낸 것입니다.

x	s를 왼쪽으로 x칸만큼 회전	올바른 괄호 문자열?
0	"{}"	O
1	"](){}["	X
2	"(){}[]"	O
3	"){}[]("	X
4	"{}"	O
5	"}{"	X

• 올바른 괄호 문자열이 되는 x가 3개이므로, 3을 return 해야 합니다.

입출력 예 #2

• 다음 표는 "}]()[{" 를 회전시킨 모습을 나타낸 것입니다.

x	s를 왼쪽으로 x칸만큼 회전	올바른 괄호 문자열?
0	"}]()[{"	X
1	"]()[{}"	X
2	"()[{}]"	O
3	")[{}]("	X
4	"{}"	O
5	"{}]()["	X

• 올바른 괄호 문자열이 되는 x가 2개이므로, 2를 return 해야 합니다.

입출력 예 #3

• s를 어떻게 회전하더라도 올바른 괄호 문자열을 만들 수 없으므로, 0을 return 해야 합니다.

입출력 예 #4

• s를 어떻게 회전하더라도 올바른 괄호 문자열을 만들 수 없으므로, 0을 return 해야 합니다.

---

나의 풀이

이번 문제는 자료구조 선택과 알고리즘 작성에 시간이 좀 걸렸다. 괄호들을 다른 형태로 치환해서 풀어보려고도 했는데, 결국 괄호는 그대로 둔 상태로 최초에 “ ( , { , [ ” 가 들어오는 경우에만 Queue에 넣고 그 후로 오는 값들을 치환해서 푸는 방식으로 넘었다.

하지만 Queue는 선입선출 방식으로 뒤에 오는 값들과의 비교 & 삭제를 진행하기에 좋은 자료구조가 아님을 깨닫고 Deque로 변경하였다.

“ ( , { , [ ” 가 들어간 이후로 “ ) , } , ] “ 가 들어오면 이를 다시 “ ( , { , [ ”로 치환하여 Deque 내부에 같은 값이 있다면 제거해주는 방식으로 진행하였는데, 이것도 하다보니 굳이 Deque를 사용할 필요 없이 선입후출 방식인 Stack을 사용하면 된다는 것을 깨달았다.

또한, 문자열을 회전 시켜주는 방법도 Deque를 사용할 때에는 임시 변수에 poll() 값을 담아주고 다시 add() 하는 방식으로 회전 시켰지만, Deque를 사용하지 않게 되었으니, String.substring() 과 charAt() 을 통해 회전을 시켜주었다.

import java.util.*;

class Solution {
    public int solution(String s) {
        int answer = 0;

        if (check(s)) {
            answer++;
        }

        for (int i = 1; i < s.length(); i++) {
            System.out.println(i);
            s = rotate(s);
            if (check(s)) {
                answer++;
            }
        }

        return answer;
    }

    public String rotate(String s) {
        s = s.substring(1) + s.charAt(0);
        return s;
    }

    public boolean check(String s) {
        Stack<Character> stack = new Stack<>();
        // ({})[]

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } else if (!stack.isEmpty()) {
                switch (c) {
                    case ')':
                        compare(stack, '(');
                        break;
                    case '}':
                        compare(stack, '{');
                        break;
                    case ']':
                        compare(stack, '[');
                        break;
                }
            } else {
                stack.push(c);
            }
            System.out.println("stack = " + stack);
        }
        return stack.isEmpty();

    }

    public void compare(Stack<Character> stack, char c) {
        if (stack.peek() == c) {
            stack.pop();
        }
    }
}