LV2 괄호 회전하기

---

문제

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

프로그래머스

풀이

기본적으로 괄호의 짝이 맞는지 검사하는 문제이다. 스택의 기본문제로 나오는데 조금 추가된건 괄호의 종류가 3가지 인것과 문자열의 길이만큼 회전을 해야한다는 것이다.

 

문자열을 회전하기 위해서는 가장 앞의 요소를 제거한다음, 뒤에 붙여야한다. 다른 방법으로는 시작인덱스와 끝 인덱스를 갱신하는 방법도 있겠지만, 나는 전자가 편하다. 그래서 앞과 뒤에 추가 및 삭제가 O(1)인 덱을 활용하기로 했다.

 

우선 덱을 하나 선언하고 문자열값을 하나씩 다 넣어준다. 이후에 문자열 길이 만큼 반복문을 돌린다. 이 반복문에서는 원본값을 가지고 회전만 수행한다. (단 첫번째에는 회전하면 안되기때문에 예외처리 해준다.)

 

그리고 괄호짝이 맞는지 검사하기 위한 for문을 하나 더 선언하고, 기존 덱을 복사한 덱을 하나 선언해서 괄호의 짝을 검사해주면 된다. 괄호의 종류가 3가지였기에 map을 활용하여 짝 검사를 간결하게 작성했다.

 

코드

import java.util.*;

class Solution {
    public int solution(String s) {
        int answer = 0;
        Map<Character, Character> m = new HashMap<>();
        m.put('[', ']');
        m.put('{', '}');
        m.put('(', ')');
        
        int len = s.length();
        Deque<Character> dq = new ArrayDeque<>();
        for(int i=0; i<len; i++) dq.addLast(s.charAt(i));
        
        for(int i=0; i<len; i++){
            if(i!=0) dq.addLast(dq.removeFirst());
            Stack<Character> st = new Stack<>();
            Deque<Character> dq_t = new ArrayDeque<>(dq);
            
            for(int j=0; j<len; j++) {
                Character ch = dq_t.removeFirst();
                if(st.empty()){
                    st.push(ch);
                } else{
                    // 짝이 맞다면
                    if(m.get(st.peek()) == ch){
                        st.pop();
                    } else{
                        st.push(ch);
                    }
                }
            }
            if(st.empty()) answer++;
        }
        return answer;
    }
}

 

후기

 

자바에선 문자열처리는 까다롭다...