9. 프로그래머스 - 괄호 회전하기 (스택)

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

• (), [], {} 는 모두 올바른 괄호 문자열입니다.
• 만약 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왼쪽으로 x칸 회전한 문자열올바른 괄호 문자열 여부

0	"{}"	O
1	"](){}["	X
2	"(){}[]"	O
3	"){}[]("	X
4	"{}"	O
5	"}{"	X

 

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

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

x왼쪽으로 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 해야 합니다.

---

주어진 문자열 s를 왼쪽으로 0칸부터 s.length()-1칸까지 회전시켜가며,
각 회전 결과가 올바른 괄호 문자열인지 판단하여 그런 경우의 수를 세는 것이 목표이다.

 

• 짝이 맞아야 함: 열면 닫아야 함 → 예: (), {[]}, ([]{})
• 순서가 맞아야 함: ([)]은 ❌ (닫는 순서가 잘못됨)
• 여는 괄호가 먼저 오고, 올바르게 닫혀야 함

회전은 문자열을 잘라서 재조합하는 것으로 구현할 수 있음

String rotated = s.substring(i) + s.substring(0, i);

 

알고리즘 코드

import java.util.Stack;

class Solution {
    public int solution(String s) {
        int count = 0;
        int len = s.length();

        for (int i = 0; i < len; i++) {
            String rotated = s.substring(i) + s.substring(0, i);
            if (isValid(rotated)) count++;
        }

        return count;
    }
    
    private boolean isValid(String s) {
        Stack<Character> st = new Stack<>();
        for (char ch : s.toCharArray()) {
            if (ch == '(' || ch == '{' || ch == '[') {
                st.push(ch);
            } else {
                if (st.isEmpty()) 
                    return false;
                char top = st.pop();
                if ((ch == ')' && top != '(') ||
                    (ch == ']' && top != '[') ||
                    (ch == '}' && top != '{')) {
                    return false;
                }
            }
        }
        return st.isEmpty();
    }
}

 

 

시간 복잡도 분석
회전마다 O(n) 문자열 생성 + O(n) 유효성 검사 O(n)×(O(n)+O(n))=O(n^2)