[PGM]괄호 회전하기

티어 : Lv. 2
정답여부 : 오답

💡문제

다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다.(), [], {} 는 모두 올바른 괄호 문자열입니다.만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다. 예를 들어, [] 가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다.만약 A, B가 올바른 괄호 문자열이라면, AB 도 올바른 괄호 문자열입니다. 예를 들어, {} 와 ([]) 가 올바른 괄호 문자열이므로, {}([]) 도 올바른 괄호 문자열입니다.대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다. 이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요.

 

제한사항

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

 

💡입출력 예

💡문제 분석 요약 

• 주어진 괄호 문자열길이만큼 회전하면서 올바른 괄호가 나오는 문자열 괄호를 구하면 되는 문제

💡알고리즘 설계

• 괄호는 짝이 맞아야 함
• 어떻게 괄호를 회전을 하며 올바른 괄호 문자열을 찾을것인가?

                     —> 괄호 문자열을 회전은 Queue 그리고 각 문자열에 있는 괄호가 짝이 맞는 경우는 stack을 이용

1. 각 문자열 길이 만큼 문자를 하나씩 큐에 넣어줌
2. 큐에 있는 문자에 열린 괄호가 있으면 stack에 값 추가
3. 괄호가 짝이 맞는경우 stack에서 빼줌 —> 만약 닫힌 괄호가 짝을 못 찾은 경우 stack에 추가
4. stack 이 비어있으면 괄호가 짝을 찾은 것으로 answer에 ++

💡시간복잡도

• O(N2)

 

💡코드

import java.util.*;

class Solution {
    public int solution(String s) {
        int answer = 0;
        Queue<Character> queue = new LinkedList<>();

        // 문자열을 큐에 넣기
        for (char c : s.toCharArray()) {
            queue.offer(c);
        }

        for (int i = 0; i < s.length(); i++) {
            Stack<Character> stack = new Stack<>();

            // 큐의 첫 번째 문자부터 처리
            for (int j = 0; j < s.length(); j++) {
                char c = queue.poll();
                queue.offer(c);

                if (stack.isEmpty()) {
                    stack.push(c);
                } else if (c == ')' && stack.peek() == '(') {
                    stack.pop();
                } else if (c == ']' && stack.peek() == '[') {
                    stack.pop();
                } else if (c == '}' && stack.peek() == '{') {
                    stack.pop();
                } else {
                    stack.push(c);
                }
            }

            if (stack.isEmpty()) {
                answer++;
            }

            // 큐의 첫 번째 문자를 뒤로 보내기
            queue.offer(queue.poll());
        }

        return answer;
    }
}

 

💡 틀린 이유

회전을 한다기에 그럼 큐를 써야하는건지 스택을 써야하는건지 고민중에 생각해보니 둘다 써도 상관은 없다고 생각했다. 둘다 사용하면 문제가 되는게 아니니..

알고리즘 설계시 괄호를 회전 하는 부분은 큐를 이용 그리고 괄호가 짝을 찾는 경우는 스택을 이용하여 문제를 풀이하였다.

다른 방법 풀이로는 해시맵을 이용하여 문제를 푸신분이 있었다.

 

💡 틀린 부분 수정 or 다른 풀이

import java.util.ArrayDeque;
import java.util.HashMap;

class Solution {
  public static int solution(String s) {
    // 괄호 정보를 저장함. 코드를 간결하게 할 수 있음
    HashMap<Character, Character> map = new HashMap<>();
    map.put(')', '(');
    map.put('}', '{');
    map.put(']', '[');

    int n = s.length(); // 원본 문자열의 길이 저장
    s += s; // 원본 문자열 뒤에 원본 문자열을 이어 붙여서 2번 나오도록 만들어줌
    int answer = 0;

    // 확인할 문자열의 시작 인덱스를 0부터 n까지 이동
    A:for (int i = 0; i < n; i++) {
      ArrayDeque<Character> stack = new ArrayDeque<>();
      // i(시작 위치)부터 원본 문자열의 길이인 n개까지 올바른 괄호 문자열인지 확인
      for (int j = i; j < i + n; j++) {
        char c = s.charAt(j);
        // 해시맵 안에 해당 키가 없다면 열리는 괄호임
        if (!map.containsKey(c)) {
          stack.push(c);
        }
        else {
          // 짝이 맞지 않으면 내부 for문은 종료하고 for문 A로 이동
          if(stack.isEmpty() || !stack.pop().equals(map.get(c)))
            continue A;
        }
      }
      // 3에서 continue 되지 않았고, 스택이 비어있으면 올바른 괄호 문자열임
      if (stack.isEmpty())
        answer++;
    }
    return answer;
  }
}

 

💡 느낀점 or 기억할정보

해시맵보단 큐와 스택 알고리즘이라 그 부분을 이용해 풀고싶었다. 저번에 풀어본 괄호에서 조금 난이도가 높은 문제였던거 같다.