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

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

프로그래머스

---

코드

import java.util.*;

class Solution {
  public int solution(String s) {
        /*
        구현 문제인 것 같다.
        큐와 스택을 이용하면 될 것 같다.
        */

        /*
        1. 큐는 문자열을 회전할 때 사용한다.
           큐에 문자열을 넣고 문자열 길이-1 만큼 poll, add 반복한다.
        2. 스택은 괄호가 올바른 지 검사할 때 사용한다.
           큐가 반복할 때마다 스택을 통해 검사한다.
           큐에서 회전이 아직 안일어난 최초 상태에도 검사를 해야한다.
           여는 괄호일 경우 스택에 바로 넣는다.
           닫는 괄호일 경우 스택 pop 했을 때 널이 아니면서
           짝꿍인 열린 괄호일 경우에만 pop을 삭제하고,
           아닐 경우에는 그냥 스택에 넣는다.
           스택이 비어있으면 정답++ 한다.
        */

    int answer = 0;
    Queue<Character> queue = new LinkedList<>();
    for(int i = 0; i < s.length(); i++){
      queue.add(s.charAt(i));
    }


    for(int i = 0; i < s.length()-1; i++){

      Stack<Character> stack = new Stack<>();
      Queue<Character> tempQueue = new LinkedList<>();
      for(Character item : queue){
        tempQueue.add(item);
      }

      for(int j = 0; j<s.length(); j++){
        if(tempQueue.peek()=='[' || tempQueue.peek()=='{' || tempQueue.peek()=='('){
          stack.push(tempQueue.poll());
        }
        else if(tempQueue.peek()==']'){
          if(!stack.empty() && stack.peek()=='[') {
            stack.pop();
            tempQueue.poll();
          }
          else stack.push(tempQueue.poll());
        }
        else if(tempQueue.peek()=='}'){
          if(!stack.empty() && stack.peek()=='{') {
            stack.pop();
            tempQueue.poll();
          }
          else stack.push(tempQueue.poll());
        }
        else if(tempQueue.peek()==')'){
          if(!stack.empty() && stack.peek()=='(') {
            stack.pop();
            tempQueue.poll();
          }
          else stack.push(tempQueue.poll());
        }
      }

      if(stack.empty()) answer++;

      queue.add(queue.poll());
    }
    System.out.println(answer);
    return answer;
  }
}

보자마자 스택과 큐를 활용하면 될 것 같다는 생각이 들었다.

구현 과정에서 큐와 스택의 요소들이 실제로 변화하는 과정을 잘 생각해야 했다.

통과는 했지만 시간적 공간적 최적화는 더 고려해봐야할 것 같다.

아래 사진처럼 메모리나 시간이 너무 많이 소요되는 것 같아서..

시간은 1시간 10분 정도 소요됬다.

최초에 스택을 이용하지 않는 방식으로 하다가 시간을 날려먹었다.

 

다른분들의 풀이를 보며 생각하는 방식을 넓히고 있다.