괄호 회전하기

작성일: 2024-11-05

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/76502

접근 방식

문자열 길이-1 만큼 회전시킨다.

회전시켰을 때, 모든 문자열이 올바른 괄호로 이루어졌을 경우에만 올바른 괄호 문자열이다.

모든 문자열을 0~n-1만큼 회전시키면서 올바른지 여부를 판단한다.

stack 자료구조를 이용해 여는 괄호는 stack에 push, 닫는 괄호인데 현재 stack이 비어있거나,

stack에서 pop(or peek) 데이터가 여는 괄호가 아닌 경우 (=짝이 이루어지지 않는 경우)

올바른 문자열이 아니라고 판단한다.

결과

소스 코드

import java.util.*;

class Solution {
    static Queue<Character> que = new LinkedList<>();
    static Map<Character, Character> map = new HashMap<>();
    public int solution(String s) {
        map.put('(', ')');
        map.put('[', ']');
        map.put('{', '}');
        int answer = 0;
        for(char t:s.toCharArray()) que.offer(t);
        for(int i=0; i<s.length(); i++){
            answer = spin(i) ? answer+1 : answer;
        }
        return answer;
    }

    boolean spin (int num){
        Queue<Character> q = new LinkedList<>(que);
        Stack<Character> stack = new Stack<>();
        boolean flag = true;
        for(int i=0; i<num; i++){
            q.offer(q.poll());
        }
        while(!q.isEmpty()){
            char cur = q.poll(); // 처리해야 할 문자
            char tmp = map.getOrDefault(cur, 'x'); // 문자가 여는 괄호인지 닫는 괄호인지
            // 닫는 괄호면서, 현재 스택의 맨 뒤 값과 대치된다면 제거
            if(tmp=='x'){
                if (stack.isEmpty() || map.get(stack.pop())!=cur) return false;
            } else stack.push(cur);
        }

        return stack.isEmpty();
    }

}

다른 접근 방식

없음.

알게 된 점

없음.