프로그래머스 lv2 괄호회전하기 자바(Java) Stack활용/ 올바른 괄호문제

기본적으로 괄호문제의 경우 스택을 사용하여 풀이를 진행합니다.

 

괄호문제에서는 스택은 선언, push, pop 만 알고있어도 쉽게 풀이가 가능합니다.

 

여기서 스택의 특징인 push 로 들어간 순서에서 
가장 마지막으로 들어간 순서 부터 꺼내는 자료구조입니다.

보통괄호 문제는 ( 일때 push 를 하고 ,   ) 가 나올때 pop 을 해서  Stack.isEmpty()를통해 스택이 비어있게 되면 올바른 괄호가 되는것입니다.

(()) 식의 중첩이나 ()() 개별 괄호를 검증할수있습니다.

이런식으로 Stack.isEmpty() 메서드를 통해 stack 이 남아있거나.

ex) ()()(  ,  ((()) <- ")" 한개 누락

아니면 ) 이 입력되었는데 지울스택이 없다면

ex) ())) , )()(

그떄는 올바른 괄호가 아닌것입니다.

 

위의 문제의 응용점은 두가지입니다

1. 단일 (,) 괄호가 아닌 [,] (,) {,} 세가지 괄호를 검증한다.

2 주어진 괄호 문자열을 한칸씩 회전을 시킨다.

 

일단 인자를 따로 나누기위해서 

split 매서드를 통해 문자열을 문자 단위로 쪼개줍니다.

그다음 괄호검증을 위한 Stack을 선언합니다.

괄호검증은  3가지 의 괄호를 분리하여 처리합니다

좌측괄호 (,{,[ 일때는 스택에 넣어주고

좌측괄호가 아닌데 스택이 비어있다면 그것은 잘못된 괄호 배열이므로 바로 break 이후 count 를 줄여줍니다.

 

우측괄호 ),},] 일때는 해당하는 짝궁괄호일때만 지워주도록합니다.

우측괄호 차례에 stack이 비어있다면 그 괄호 배열은 잘못된 괄호배열입니다.

만약에 지우지 못한다면 stack 에 쌓이기 때문에 잘못된 괄호입니다.

============================================================================================

 

이번에는 괄호 문자열 회전을 위한 반복문 적용입니다

위의 코드에 for 문을 적용시킵니다.

s문자열의 길이만큼 한글자 씩 뒤로 돕니다. 

while 문에서 문자열의 문자수만큼 반복문을 돌려주도록 합니다.

 

이외에 2가지 방법이 더있지만 사용하지않았습니다

 

물론 substring 을 이용하여 문자열을 뒤로 한칸씩 밀어도되지만.

그렇게 되면 다시 배열선언을 해야합니다. 그렇게되면 시간 효율성을 놓치게 되겠죠

 

두번째로 배열을 다시선언하거나 arraylist를 이용하여 배열위치를 변경할수있습니다.

이경우 역시 arraylist 를 remove 하고 add 할때 시간복잡도를 소모하므로 사용하지 않았습니다.

 

정답코드는 아래

import java.util.Stack;

public class RotatingParentheses {
    public int solution(String s) {
        int answer = 0;
        String[] arr = s.split("");
        Stack<String> stack = new Stack<>();
        for(int i=0; i<arr.length;i++) {
            int j=0;
            int k=i;
           while (j< arr.length) {
                String letter = arr[k% arr.length];
                if (letter.equals("(") || letter.equals("[") || letter.equals("{")) {
                    stack.add(letter);
                } else {
                    if(stack.isEmpty()){
                        answer--;
                        break;
                    }
                    if (letter.equals(")")&&stack.peek().equals("(")) {
                            stack.pop();
                    } else if (letter.equals("]")&&stack.peek().equals("[")) {
                            stack.pop();
                    } else {
                        if (stack.peek().equals("{")) {
                            stack.pop();
                        }
                    }
                }
                j++;
                k++;
            }
            if (stack.isEmpty()) {
                answer++;
            }
        }
        return answer;
    }
}

 

위의 코드나 해설이 이해안되시면 댓글남겨주시면 설명해드리겠습니다