코딩 테스트 [프로그래머스] - 괄호 회전하기

문제 링크

괄호의 시작이 늦게 나올수록 괄호의 끝이 빨리 나와야 되는 특성에서
후입 선출의 특징을 가진 Stack 이용해 문제를 풀었다.

---

전체 코드는 다음과 같다.

import java.util.*;

class Solution {
    public int solution(String s) {
        int answer = 0;
        
        String original = s;
        Stack<Character> stack = new Stack<>();
        boolean roop = true;
        
        while(roop){
            s = s.substring(1,s.length()) + s.substring(0, 1);
            if(s.equals(original))
                roop = false;
            
            char[] c = s.toCharArray();
            boolean isPossible = true;
            
            for(int i = 0; i < c.length; i++){
                char now = c[i];
                
                if(now == '[')
                    stack.add(']');
                else if(now == '{')
                    stack.add('}');
                else if(now == '(')
                    stack.add(')');
                else{
                    if(stack.isEmpty()){
                        isPossible = false;
                    }else{
                        char pop = stack.pop();
                        if(now != pop){
                            isPossible = false;
                        }
                    }
                }  
            }
            
            if(!stack.isEmpty())
                isPossible = false;
            
            if(isPossible)
                answer++;
            
            stack.clear();
        }
        
        return answer;
    }
}

---

원본 문자열을 저장할 original,
괄호의 끝이 나와야 할 순서대로 괄호를 저장할 stack,
반복문의 끝을 나타낼 roop를 만들었다.

        String original = s;
        Stack<Character> stack = new Stack<>();
        boolean roop = true;

주어진 문자열 s를 왼쪽으로 한 번 씩 회전시키며 문자열을 저장한다.
만약 이 문자열이 원본과 같다면 이번 문자열을 마지막으로 반복을 종료한다.
주어진 문자열을 char 배열로 만들어 저장하고,
지금 문자열이 올바른 괄호 문자열인지 나타내는 isPossible을 true로 초기화했다.

        while(roop){
            s = s.substring(1,s.length()) + s.substring(0, 1);
            if(s.equals(original))
                roop = false;
            
            char[] c = s.toCharArray();
            boolean isPossible = true;

char 배열의 길이(문자열의 길이)만큼 반복하며 각 문자를 가져온다.
만약 지금 문자가 괄호의 시작이라면 해당하는 괄호를 닫는 문자를 stack에 집어넣는다.

            for(int i = 0; i < c.length; i++){
                char now = c[i];
                
                if(now == '[')
                    stack.add(']');
                else if(now == '{')
                    stack.add('}');
                else if(now == '(')
                    stack.add(')');

만약 그 외의 경우(닫는 괄호가 나온 경우)엔
먼저 stack이 비어있는지 확인한다.
stack이 비어있는데 닫는 괄호가 나왔다는 것은 올바르지 않은 괄호 문자열이라는 뜻이므로 isPossible을 false로 바꾼다.
stack이 비어있지 않다면 stack에서 값을 pop()해 지금 값과 비교한다.
두 값이 틀리다면 이또한 올바르지 않은 괄호 문자열이라는 뜻이므로 isPossible을 false로 바꾼다.

            for(int i = 0; i < c.length; i++){
                char now = c[i];
                
                if(now == '[')
                    ...
                else if(now == '{')
                    ...
                else if(now == '(')
                    ...
                    
                else{
                    if(stack.isEmpty()){
                        isPossible = false;
                    }else{
                        char pop = stack.pop();
                        if(now != pop){
                            isPossible = false;
                        }
                    }
                }  
            }

반복문이 끝났다면 먼저 stack이 비어있는지 확인한다.
stack에 값이 남아있다면 괄호의 시작만 있고 끝이 없는 경우가 존재한다는 뜻이므로 올바르지 않은 괄호 문자열이 된다(isPossible = false)

isPossible 값이 true라면 지금 문자열은 올바른 괄호 문자열이라는 뜻이므로 정답에 1을 더한다.

그 후 stack의 값을 비운다.

            for(int i = 0; i < c.length; i++){
                ...  
            }
            
            if(!stack.isEmpty())
                isPossible = false;
            
            if(isPossible)
                answer++;
            
            stack.clear();
        }

---

마지막에 stack의 값이 비어있는 지 확인해줘야 하는 부분을 생각해내는데 시간이 걸렸다.