[Java/자바] 프로그래머스 Lv2 - 괄호 회전하기 (스택 Stack 활용)

문제 설명

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

• (), [], {} 는 모두 올바른 괄호 문자열입니다.
• 만약 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

 

 

입출력 예 설명

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

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

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

 

---

Solution.java

이 문제는 프로그래머스 문제의 "짝지어 제거하기"처럼 Stack을 이용하여 올바른 괄호 짝을 Stack에서 제거하면서

문자열이 올바른 괄호 짝으로 이뤄진 문자열인지 확인합니다.

 

회전은 맨 앞의 문자를 뒤로 옮기면서 그 문자열이 올바른 괄호 쌍으로 이뤄져있는지 확인합니다.

그리고 올바른 괄호 일 때마다 count를 1씩 늘립니다.

 

import java.util.Stack;

public class 괄호회전 {
    public static void main(String[] args) {
        System.out.println(solution("[](){}"));
        System.out.println(solution("}]()[{"));
        System.out.println(solution("[)(]"));
    }

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

        for (int i = 0; i < s.length(); i++) {
            StringBuilder str = new StringBuilder(s);
            // 만 앞의 문자열을 맨 뒤로 옮겨 회전
            String rotation = str.substring(0, i);
            str.delete(0,i);
            str.append(rotation);

            if(checkStr(str)){
                answer += 1;
            }
        }
        return answer;
    }

    public static boolean checkStr(StringBuilder str) {
        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (stack.isEmpty()) {
                stack.push(c);
            } else {
                if (c == ']') {
                    if (stack.peek() == '[') {
                        stack.pop();
                    } else {
                        stack.push(c);
                    }
                } else if (c == ')') {
                    if (stack.peek() == '(') {
                        stack.pop();
                    } else {
                        stack.push(c);
                    }
                } else if (c == '}') {
                    if (stack.peek() == '{') {
                        stack.pop();
                    } else {
                        stack.push(c);
                    }
                } else {
                    stack.push(c);
                }
            }
        }

        if (stack.isEmpty()) {
            return true;
        } else {
            return false;
        }
    }
}

문제 풀이

1. 회전한 문자열을 확인할 함수를 만듭니다. (checkStr)
2. stack이 비었다면 문자열(str)을 i 번째 문자열을 삽입합니다.
3. stack이 비지 않았다면 문자열의 i번째와 그 앞에 있는 문자가 올바른 쌍인지 확인하고, 올바른 쌍이라면 넣었던 문자를 제거합니다.
4. stack이 비지 않았지만 문자열의 i번째와 그 앞에 있는 문자가 올바른 쌍이 아니라면, 문자열의 i번째 문자를 삽입합니다.
5. 반복문이 종료되고 완성된 stack이 비었다면 모든 괄호가 올바른 쌍으로 이뤄져있으므로 true를, 아니라면 false를 반환합니다.

문제 이해가 어렵다면 아래 출력문을 보면서 좀더 쉽게 이해가 가능할 겁니다.