괄호 회전하기

💡 문제

다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다.

• (), [], {} 는 모두 올바른 괄호 문자열입니다.
• 만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다. 예를 들어, [] 가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다.
• 만약 A, B가 올바른 괄호 문자열이라면, AB 도 올바른 괄호 문자열입니다. 예를 들어, {} 와 ([]) 가 올바른 괄호 문자열이므로, {}([]) 도 올바른 괄호 문자열입니다.

대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다. 이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요.

 

💡 제한사항

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

입출력 예

입출력 예 #1

• 다음 표는 "[](){}" 를 회전시킨 모습을 나타낸 것입니다.

• 올바른 괄호 문자열이 되는 x가 3개이므로, 3을 return 해야 합니다.

입출력 예 #2

• 다음 표는 "}]()[{" 를 회전시킨 모습을 나타낸 것입니다.

 

• 올바른 괄호 문자열이 되는 x가 2개이므로, 2를 return 해야 합니다.

입출력 예 #3

• s를 어떻게 회전하더라도 올바른 괄호 문자열을 만들 수 없으므로, 0을 return 해야 합니다.

입출력 예 #4

• s를 어떻게 회전하더라도 올바른 괄호 문자열을 만들 수 없으므로, 0을 return 해야 합니다.

 

✨ 풀이

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

class Solution {
    public int solution(String s) {
    Deque<String> deq = new ArrayDeque<>();
    Stack<String> stack = new Stack<>();
    int answer = 0;

    for (int i = 0; i < s.length(); i++) {
      deq.add(String.valueOf(s.charAt(i)));
    }

    for (int i = 0; i < s.length(); i++) {
      stack.clear();
      for (String j : deq) {
        if (stack.empty()) {
          stack.push(j);
        } else {
          if (stack.peek().equals("{") && j.equals("}")) {
            stack.pop();
          } else if (stack.peek().equals("[") && j.equals("]")) {
            stack.pop();
          } else if (stack.peek().equals("(") && j.equals(")")) {
            stack.pop();
          } else {
            stack.push(j);
          }
        }
      }
      if (stack.empty()) {
        answer++;
      }
      deq.add(deq.removeFirst());
    }
    return answer;
  }
}

해당 문제는 못풀었다. 다른 글을 참고했는데, 큐와 스택을 이용해서 푸는 문제라고 힌트를 받아서 다시 풀었다. 기존에 괄호 짝 찾는 문제에서 stack으로 푸는 방식에 수열 순회 문제에서 풀었던 deque를 조합했다. 풀이는 다음과 같다.

1. 전달받은 문자열을 deque로 만든다.
2. 문자열 길이만큼 반복한다. 반복 시 스택을 초기화 시킨다.
3. 반복문 내에서 deque만큼 반복시킨다.
4. 최초 반복시 스택은 비어있기 때문에 스택을 추가하고, 스택이 비어있지 않다면 스택에 추가된 각 괄호를 비교한다. 만약 같은 문자가 없다면 스택을 다시 추가한다.
5. 만약에 스택이 비어 있다면, 올바른 괄호 문자열이기 때문에 answer에 값을 1 증가시킨다.
6. dequq의 왼쪽에 있는 값을 오른쪽으로 이동시킨다.

출처

https://school.programmers.co.kr/learn/challenges