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

https://school.programmers.co.kr/learn/courses/30/lessons/76502

프로그래머스

 

0️⃣

문제

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

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

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

 

입력

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

 

1️⃣ 어떻게 문제를 풀까?

: 괄호처럼 짝 짓는 문제는 스택을 이용해서 풀 수 있다! (Lv.1에도 비슷한 문제가 있음) but 이번 문제는 괄호의 종료가 다양([], {}, ())하고 전체 문자열 s를 바꿔가면서 올바른 괄호인지 확인한다! (2중 for문은 불가피할 것 같은데..)

 

일단 생각했던대로 풀어보자!

 

1) 첫번째 풀이

import java.util.*;

class Solution {
    public int solution(String s) {
        int answer = 0;
        int n = s.length();
        HashMap<Character, Character> hash = new HashMap<>();
        hash.put(']', '[');
        hash.put(')', '(');
        hash.put('}', '{');
        
        for(int i = 0; i < n; ++i) {
            Stack<Character> stack = new Stack<>();
            for(int j = 0; j < n; ++j) {
                int index = (i + j >= n) ? i + j - n : i + j;
             
                char c = s.charAt(index);
                if(c == '[' || c == '(' || c == '{') {
                    stack.push(c);
                    continue;
                } else {
                    if(!stack.isEmpty() && stack.peek() == hash.get(c)) {
                        stack.pop();
                        continue;
                    } else {
                        stack.push(c);
                        break;
                    }
                }
            }
            if(stack.isEmpty()) answer++;   
        }
        
        return answer;
    }
}