[Java] 프로그래머스 : 괄호 회전하기

반응형

[Java] 프로그래머스 : 괄호 회전하기

 

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

프로그래머스

---

접근

괄호 열고 닫는 스택 관련 문제는 다 비슷한 방식으로 풀리기 때문에 걱정이 없었으나, 이번에는 주어진 문자열을 회전하는 방법이 잘 떠오르지 않았습니다.

 

올바른 괄호 문자열 검증 방법

여는 괄호가 나올 경우 push
닫는 괄호가 나올 경우 스택이 비어있으면 break,
닫는 괄호가 나올 경우 스택 맨 위의 값이 짝이 맞는 여는 괄호일 경우 pop

마지막에 스택이 비어 있는 경우에 answer++;

 

하지만 여기서 어떻게 해야 주어진 문자열을 계속 회전하면서 검증할지가 고민이었습니다.

 

처음에는 StringBuilder와 setCharAt 메서드로 검증이 끝날 때 마다 문자열을 회전시킨뒤 s에 재할당하는 방법을 적용했으나 시간초과가 나왔습니다.

 

그러다 잘 생각해보니 스택으로 문자열을 검증하는 시작 인덱스 위치를 바꿔주면 될 것 같았습니다.

 

일반적으로 회전을 0번 할 경우, index 0번부터 s.length - 1번 동안 인덱스를 증가시키며 반복문을 순회하게 될 것입니다.

회전을 1번 할 경우, index 1번부터 s.length - 1번 동안 인덱스를 증가시키며 반복문을 순회합니다. 그러나 마지막 인덱스가 문자열 s 범위를 초과하게 됩니다.

 

그래서 아래와 방법을 떠올리게 되었습니다.

rotaion이란 값을 추가해서 i + rotation의 값이 s의 범위 내에서 s.length - 1번 반복문을 돌릴 수 있도록 구현하였습니다.

 

그러다가 i가 필요한 만큼 반복을 끝냈을 때 스택이 비어있는 경우에만 answer를 카운트합니다.

 for (int rotation = 0; rotation < s.length(); rotation++) {
            stack.clear();
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt((i + rotation) % s.length())
                ...(스택으로 올바른 괄호 문자열인지 확인하는 코드)
                
                if (i == s.length() - 1 && stack.isEmpty()) {
                    answer++;
                }

 

 

전체 코드

import java.util.*;
class Solution {
    public int solution(String s) {
        int answer = 0;
        Stack<Character> stack = new Stack<>();
        
        for (int rotation = 0; rotation < s.length(); rotation++) {
            stack.clear();
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt((i + rotation) % s.length());
                
                if (c == '[' || c == '(' || c == '{') {
                    stack.push(c);
                }
                else {
                    if (stack.isEmpty()) {
                        break;
                    }
                    char top = stack.peek();
                    if ( (top == '(' && c == ')') || (top == '{' && c == '}') || (top == '[' && c == ']') ) {
                        stack.pop();
                    }
                    else {
                        break;
                    }
                }
                
                if (i == s.length() - 1 && stack.isEmpty()) {
                    answer++;
                }
            }
        }
        return answer;
    }
}