99클럽 코테 스터디 28일차 TIL - [프로그래머스] 괄호 회전하기 (Java)

📌 오늘의 학습 키워드

[프로그래머스] 괄호 회전하기 (Java)
https://school.programmers.co.kr/learn/courses/30/lessons/76502

📌 공부한 내용 본인의 언어로 정리하기

문제 탐색하기

입력 : 대괄호, 중괄호, 소괄호로 이루어진 문자열 s (1 ≤ s의 길이 ≤ 1,000)
출력 : s가 올바른 괄호 문자열이 되게 하는 x의 개수 (0 ≤ x < (s의 길이))

가능한 시간복잡도

O(n)

알고리즘 선택

해시맵, 스택

📌 코드 설계하기

1. 문자열을 왼쪽으로 한 칸씩 회전시키며 반복한다.
2. 회전된 문자열이 올바른 괄호 문자열인지 확인한다.
3. 문자를 하나씩 읽어가며 여는 괄호는 스택에 넣는다.
4. 닫는 괄호가 나오면 HashMap을 사용해 매칭되는 여는 괄호를 찾고, 스택에서 꺼낸다.
5. 매칭되지 않으면 올바르지 않은 문자열로 간주해 false를 반환한다.
6. 올바른 괄호 문자열인 경우의 수를 리턴한다.

📌 오늘의 회고

어떤 문제가 있었고, 나는 어떤 시도를 했는지

어떻게 해결했는지

무엇을 새롭게 알았는지

내일 학습할 것은 무엇인지

구현

📌 정답 코드

import java.util.*;

class Solution {
    public int solution(String s) {
        int count = 0;
        int n = s.length();
        
        for (int i = 0; i < n; i++) {
            if (isValid(s)) {
                count++;
            }
            // 문자열 회전
            s = s.substring(1) + s.charAt(0);
        }
        
        return count;
    }
    
    private boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        HashMap<Character, Character> map = new HashMap<>();
        map.put(')', '(');
        map.put('}', '{');
        map.put(']', '[');
        
        for (char c : s.toCharArray()) {
            if (map.containsKey(c)) {
                // 닫는 괄호가 나왔을 때 스택이 비어있거나 매칭되지 않으면 false
                if (stack.isEmpty() || stack.pop() != map.get(c)) {
                    return false;
                }
            } else {
                // 여는 괄호는 스택에 넣기
                stack.push(c);
            }
        }
        
        return stack.isEmpty();
    }
}