[Java] 괄호 회전하기

괄호 회전하기

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

class Solution {

  public int solution(String s) {
    int answer = 0;
    // 문자열을 리스트에 저장
    List<Character> sList = new LinkedList<>();
    for (char c : s.toCharArray()) {
      sList.add(c);
    }

    int l = s.length();
    for (int i = 0; i < l; i++) {
      // 현재 리스트가 유효한 괄호 문자열인 경우 정답을 증가시킴
      if (isValid(sList)) {
        answer += 1;
      }
      // 문자열을 한 칸 회전시킴
      sList.add(0, sList.get(sList.size() - 1));
      sList.remove(sList.size() - 1);
    }
    return answer;
  }

  // 주어진 리스트가 유효한 괄호 문자열인지 확인하는 메서드
  private boolean isValid(List<Character> sList) {
    Deque<Character> stack = new ArrayDeque<>(); // 스택을 이용하여 괄호 매칭 확인
    HashMap<Character, Character> map = new HashMap<>(); // 매칭 정보를 담은 해시맵
    map.put('(', ')');
    map.put('[', ']');
    map.put('{', '}');

    for (char c : sList) {
      if (map.containsKey(c)) { // 여는 괄호일 경우 스택에 push
        stack.push(c);
      } else { // 닫는 괄호일 경우
        if (stack.isEmpty()) { // 스택이 비어있으면 불일치
          return false;
        }
        if (map.get(stack.peek()) != c) { // 스택의 맨 위 괄호와 일치하지 않으면 불일치
          return false;
        }
        stack.pop(); // 일치하면 스택에서 pop
      }
    }
    return stack.isEmpty(); // 스택이 비어있으면 모든 괄호가 정상적으로 매칭됨
  }

}

요점 정리:

1. 문제 설명:
   주어진 문자열을 왼쪽으로 회전시키며 각 회전된 문자열이 유효한 괄호 문자열인 경우를 세는 문제입니다.

2. 문제 해결 방법:

   • 문자열을 리스트로 변환하여 처리합니다.
   • 각 회전된 문자열이 유효한 괄호 문자열인지 확인하는 isValid 메서드를 구현합니다.
   • 스택을 사용하여 괄호의 쌍이 맞는지 검사합니다. 여는 괄호는 스택에 push하고, 닫는 괄호는 스택의 맨 위와 매칭하여 pop 합니다.
   • 모든 문자열 회전에 대해 isValid를 호출하여 정답을 계산합니다.

3. 구현 상세:

   • solution 메서드: 문자열을 회전하며 isValid가 true일 때마다 answer를 증가시킵니다.
   • isValid 메서드: 주어진 리스트가 유효한 괄호 문자열인지 확인합니다. 해시맵을 이용하여 괄호의 매칭 관계를 정의하고, 스택을 이용하여 매칭 여부를 확인합니다.

4. 주의할 점:

   • 회전 연산은 리스트의 add와 remove 메서드를 사용하여 구현했습니다.
   • 스택의 isEmpty, push, pop, peek 메서드를 활용하여 괄호 매칭을 검사했습니다.

이 코드는 문자열을 회전시키며 모든 가능한 경우의 수를 탐색하고, 각 경우에 대해 유효성을 검사하여 문제를 해결하는 방식으로 구현되어 있습니다.