프로그래머스 2단계 : 괄호 회전하기 (Java 자바)

문제 설명

 

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

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

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

 

 

제한사항

 

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

 

입출력 예

 

 

 

풀이

 

주어진 문자열 s를 회전시키면서 올바른 괄호 문자열이 되는 경우의 수를 계산하는 문제입니다. 괄호 문자열의 올바른 조건과 회전하는 과정을 검사하여 가능한 회전 횟수를 찾습니다.

 

1. 초기에 회전 횟수를 저장할 answer 변수를 초기화합니다.

2. 주어진 문자열 s의 각 문자를 큐에 추가합니다.

3. 문자열을 왼쪽으로 회전하면서 가능한 회전 횟수를 찾기 위해 for 루프를 사용합니다.

4. 회전한 문자열을 스택을 사용하여 검사하면서 괄호 짝을 확인합니다.

5. 스택이 비어있다면, 현재 회전된 문자열은 올바른 괄호 문자열이므로 answer를 증가시킵니다.

6. 모든 회전에 대해 위 과정을 반복하고, 최종적으로 answer를 반환합니다.

7. 문자열 s를 회전시키면서 올바른 괄호 문자열이 되는 경우를 계산하고, 그 개수를 반환합니다.

 

import java.util.*;

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

        Queue<String> queue = new LinkedList<>();

        // 문자열 s의 각 문자를 큐에 추가합니다.
        for (int i = 0; i < s.length(); i++) {
            String str = s.substring(i, i + 1);
            queue.add(str);
        }

        // 문자열을 왼쪽으로 회전하면서 가능한 경우를 검사합니다.
        for (int i = 0; i < s.length(); i++) {
            String firstStr = queue.poll();
            queue.add(firstStr);

            Stack<String> stack = new Stack<>();

            // 문자열을 스택에 넣으면서 괄호 짝을 검사합니다.
            for (int j = 0; j < s.length(); j++) {
                String waitingStr = queue.poll();
                queue.add(waitingStr);

                if (stack.isEmpty()) {
                    stack.push(waitingStr);
                } else if (waitingStr.equals(")") && stack.peek().equals("(")) {
                    stack.pop();
                } else if (waitingStr.equals("]") && stack.peek().equals("[")) {
                    stack.pop();
                } else if (waitingStr.equals("}") && stack.peek().equals("{")) {
                    stack.pop();
                } else {
                    stack.push(waitingStr);
                }
            }

            // 스택이 비어있다면 올바른 괄호 문자열이므로 회전 횟수를 증가시킵니다.
            if (stack.isEmpty()) {
                answer++;
            }
        }

        return answer;
    }
}