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

문제

주어진 문자열 s에 대해, 문자열을 왼쪽으로 한 칸씩 회전하면서 올바른 괄호 문자열인지 판단합니다. 모든 회전 경우에 대해 올바른 괄호 문자열의 개수를 반환하는 문제입니다.

🛠 사용 기술

• Stack
• 슬라이딩 인덱스

Approach 1

🔍 접근법

하나의 stack을 선언하고 매 루프마다 현재 선택된 문자와 stack 맨위의 값을 비교해서 괄호짝이 맞는지 확인합니다. 회전된 문자열에서 새로운 인덱스를 구하는건 % 연산을 통해 구했지만, queue를 사용하면 더 직관적으로 구할 수 있습니다. 테스트케이스 13번에서 통과하지 못해 많이 해맸는데 원인은 다음과 같았습니다. 루프 내부에서 괄호 짝이 맞지 않을 경우 check 플래그를 false로 바꾸긴 했지만, 모든 문자가 열린 괄호인 경우, 예를 들어 "((("인 경우에는 루프를 무사히 통과하게 됩니다. 이 경우에는 스택에 열린 괄호가 남아 있음에도 불구하고 check == true 조건을 만족하여 잘못된 문자열을 올바른 것으로 간주하게 됩니다.

💻 코드

import java.util.*;

class Solution {
    public int solution(String s) {
        int n = s.length();
        
        int cnt = 0;
        for(int i=0; i<n; i++){
            Stack<Character> stack = new Stack<>();
            boolean check = true;
            
            innerLoop:
            for(int j=0; j<n; j++){
                int index = (j+i) % n;
                char c = s.charAt(index); // 선택된 문자
                
                if(c == '[' || c == '(' || c == '{'){
                    stack.push(c);
                }else{
                    if(stack.isEmpty()){ // 닫힌 괄호가 들어갈 차례에 열린 괄호가 스택에 x -> 실패
                        check = false;
                        break innerLoop;
                    }else{
                        char top = stack.pop();
                        if((c == ']' && top != '[') || (c == ')' && top != '(') || (c == '}' && top != '{')){ // 짝이 맞지 않는 경우 -> 실패
                            check = false;
                            break innerLoop;
                        }  
                    }
                }
            }
            if(check == true) {
                cnt++;
            }
        }
        return cnt;
    }
}

Approach 2 ⭕

🔍 접근법

열린 괄호만 입력되는 경우를 고려하여 stack이 비어있는지 확인하는 로직을 추가했습니다.

1. 회전된 문자열에서 각 문자를 하나씩 스택에 푸시/팝 하며 괄호 검증
2. 반복문 종료 후 스택이 비어 있는지 확인하여 최종 유효성 판단

💻 코드

import java.util.*;

class Solution {
    public int solution(String s) {
        int n = s.length();
        
        int cnt = 0;
        for(int i=0; i<n; i++){
            Stack<Character> stack = new Stack<>();
            boolean check = true;
            
            innerLoop:
            for(int j=0; j<n; j++){
                int index = (j+i) % n;
                char c = s.charAt(index); // 선택된 문자
                
                if(c == '[' || c == '(' || c == '{'){
                    stack.push(c);
                }else{
                    if(stack.isEmpty()){ // 닫힌 괄호가 들어갈 차례에 열린 괄호가 스택에 x -> 실패
                        check = false;
                        break innerLoop;
                    }else{
                        char top = stack.pop();
                        if((c == ']' && top != '[') || (c == ')' && top != '(') || (c == '}' && top != '{')){ // 짝이 맞지 않는 경우 -> 실패
                            check = false;
                            break innerLoop;
                        }  
                    }
                }
            }
            if(!stack.isEmpty()){ //스택이 비어있는지 확인
                check = false;
            }
            if(check == true) {
                cnt++;
            }
        }
        return cnt;
    }
}

느낀 점 및 메모 💡

• 회전 인덱스는 index = (i + j) % n 방식으로 처리하면 큐 없이도 간단하게 구현할 수 있다.
• 하지만 가독성과 명확한 표현을 원한다면 Queue로 문제를 푸는 것도 좋은 선택이다.

---