Skip to main content

[Java] 76502 괄호 회전하기

📝 괄호 회전하기

1. 문제 요약

  • 문자열 s는 (), [], {} 괄호로만 이루어져 있다.
  • 문자열 s를 왼쪽으로 x칸 회전시킬 수 있다.
    • 예: s = "[]()", x=1 → "]()["
  • 회전된 문자열이 올바른 괄호 문자열이라면 카운트한다.
    • 0 ≤ x < s.length 범위 안에서 가능한 경우의 수를 모두 세어 정답으로 반환한다.

👉 올바른 괄호 문자열 조건

  • (), [], {} 자체는 올바르다.
  • 올바른 괄호 문자열을 괄호로 감싸도 올바르다.
    • 예: [] → ([]) 가능
  • 올바른 괄호 문자열을 이어 붙여도 올바르다.
    • 예: {} + ([]) → { } ( [ ] )

image.png

2. 접근 방식

  1. ​회전 어떻게 구현?
    • substring으로 구현
  2. 올바른지 어떻게 확인?
    • 열린 괄호면 → push
    • 닫는 괄호면
      • 안 비었으면 → pop() 해서 top이랑 지금 닫는 괄호가 맞는지 확인
      • 먼저 스택이 비었는지 확인
      • 비었으면 → 짝이 없으니까 false

3. 오답 / 어려웠던 점

import java.util.*;

class Solution {
    public int solution(String s) {
        int answer = -1;
        int n = s.length();
        
        for (int i = 0; i < n; i++) {
            String rotated = s.substring(i) + s.substring(0, i);
            if (isValid(rotated)) answer++;
        }
        
        return answer;
    }
    
    public boolean isValid(String str) {
        Stack<Character> isValid = new Stack<>();
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '(' || 
                str.charAt(i) == '[' || 
                str.charAt(i) == '{' ) {
                isValid.push(str.charAt(i));
            } else {
                // 닫는 괄호일 때                
                char top = isValid.pop();
                if (str.charAt(i) == ')' && top != '(') return false;
                if (str.charAt(i) == ']' && top != '[') return false;
                if (str.charAt(i) == '}' && top != '{') return false;
            }
        }
        
        // 모두 처리하고 나서 스택이 비어있으면 올바른 괄호 문자열
        return isValid.isEmpty();
    }
}
  1. answer 초기값을 -1로 지정하는 실수 (프로그래머스 디폴트)
  2. 스택 오버플로우 예외처리 안함

닫는 괄호 처리할 때 스택이 비었는지 먼저 검사해야 하는 이유

if (isValid.isEmpty()) return false;

1) 스택 언더플로우 예외 처리

예를 들어 입력 문자열이 ")(" 라고 해보자.

  1. 첫 번째 문자 ')'를 만났을 때 → 닫는 괄호임
  2. 그런데 스택은 아직 비어있음. (앞에서 여는 괄호 '('가 없었음)
  3. 이 상태에서 pop()을 하면?
    • 에러 발생 (스택 언더플로우)
    • 논리적으로도 말이 안 됨. 닫는 괄호를 꺼낼 여는 괄호가 없는데 pop을 하면 안 됨

그래서 항상 pop() 하기 전에 먼저 체크하는 것임

2) 올바른 괄호 검증

// 닫는 괄호일 때
if (isValid.isEmpty()) return false;

char top = isValid.pop();
if (str.charAt(i) == ')' && top != '(') return false;
if (str.charAt(i) == ']' && top != '[') return false;
if (str.charAt(i) == '}' && top != '{') return false;
  • 닫는 괄호를 처리할 때는 반드시 매칭할 열린 괄호가 스택에 들어있어야 함
  • 근데 스택이 비어 있다면 → 짝이 안 맞는다는 뜻이니까 false로 바로 리턴해야 함

4. 정답코드

import java.util.*;

class Solution {
    public int solution(String s) {
        int answer = 0;
        int n = s.length();
        
        for (int i = 0; i < n; i++) {
            String rotated = s.substring(i) + s.substring(0, i);
            if (isValid(rotated)) answer++;
        }
        
        return answer;
    }
    
    public boolean isValid(String str) {
        Stack<Character> isValid = new Stack<>();
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '(' || 
                str.charAt(i) == '[' || 
                str.charAt(i) == '{' ) {
                isValid.push(str.charAt(i));
            } else {
                // 닫는 괄호일 때
                if (isValid.isEmpty()) return false;
                
                char top = isValid.pop();
                if (str.charAt(i) == ')' && top != '(') return false;
                if (str.charAt(i) == ']' && top != '[') return false;
                if (str.charAt(i) == '}' && top != '{') return false;
            }
        }
        
        // 모두 처리하고 나서 스택이 비어있으면 올바른 괄호 문자열
        return isValid.isEmpty();
    }
}



Back to top