[Java] Lv2. 괄호 회전하기

🔗 문제 링크

프로그래머스

 

📝 문제 설명

• 다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다.
  • (), [], {} 는 모두 올바른 괄호 문자열입니다.
  • 만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다. 예를 들어, [] 가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다.
  • 만약 A, B가 올바른 괄호 문자열이라면, AB 도 올바른 괄호 문자열입니다. 예를 들어, {} 와 ([]) 가 올바른 괄호 문자열이므로, {}([]) 도 올바른 괄호 문자열입니다.
• 대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다. 이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요

 

⚠️ 제한 사항

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

 

✨ 내 코드

import java.util.HashMap;
import java.util.Stack;

class Solution {
    public int solution(String s) {
        
        // 괄호 짝 지어놓기
        HashMap<Character, Character> map = new HashMap<>();
        map.put(')', '(');
        map.put(']', '[');
        map.put('}', '{');
        
        int answer = 0;
        char[] a = s.toCharArray();
        for(int i = 0; i < s.length(); i++) {
            Stack<Character> stack = new Stack<>();
            
            // 올바르지 않은 괄호 문자열 발생 플래그
            boolean flag = true;
            
            for(int j = 0; j < s.length(); j++) {
                if(flag) {
                    // out of bound 예외가 발생하지 않도록 mod 연산으로 가져오기
                    char c = s.charAt((i+j) % s.length());
                    
                    // 여는 괄호이면 push
                    if(c == '(' || c == '{' || c == '[') {
                        stack.push(c);

                    } else {
                        // 닫는 괄호 차례일 때 스택이 비었거나, 짝이 안 맞으면
                        if (stack.isEmpty() || stack.pop() != map.get(c)) {
                            
                            // 플래그를 false로 전환
                            flag = false;
                            continue;
                        }
                    }
                }
            }
            
            // 한 바퀴 돌았을 때 플래그 확인 후 answer 값 갱신
            if(flag && stack.isEmpty()) {
                answer++;
            }
        }
        return answer;
    }
}

 

💡 풀이

1. 닫는 괄호와 여는 괄호를 짝 지어 Hashmap에 저장한다.(검색에 용이하게)
2. 올바르지 않은 괄호 문자열 발생 플래그를 선언한다
3. 이중 for문으로 문자열을 회전시킨다.
4. 여는 괄호면 스택에 push한다.
5. 닫는 괄호일 때 스택이 비었거나 가장 최신에 삽입한 값과 다르면 플래그를 false로 바꾼다
6. 안쪽 반복문을 한 바퀴 돌았을 때 플래그 값과 스택을 확인한 후 answer값을 갱신한다.

 

💭 회고

처음엔 괄호를 2차원 배열로 짝지어 놨는데 이 방법은 닫힌 괄호일 때 5번을 확인하기 어려웠다.

뭔가 플래그라는 것을 오랜만에 활용한 것 같은데 이 방법을 쓰면 안쪽 반복문을 아예 무시할 수 있으니 좋은 것 같다.

앞으로 문제 풀 때는

• 짝지어야 할 때는 HashMap