[프로그래머스] JAVA LV2 "올바른 괄호" 풀이방법 / 스택 사용

스택 알고리즘에서 자주 다루는 () 괄호 문제.

 

전공 책만 봐도 기본으로 나오는 예제인 것 같다.

 

그래서 막힘없이 술술 풀릴정도라, 왜 LV2인지는 모르겠으나.. 안 접해본 사람이라면 고민은 해볼 수 있을정도!

 

본론으로 들어가자면..

 

스택 (Stack)

• 후입선출(LIFO) 방식의 자료구조.
• 즉, 나중에 들어간 것이 가장 먼저 나오는 구조이다.

이 스택을 어떻게 괄호 문제에 활용할 수 있을까?

 

괄호가 열리면, 반드시 짝이되는 닫는 괄호가 있어야 한다.

괄호가 열릴 때마다 저장해 두었다가 닫는 괄호를 만나면 하나씩 삭제해 나가면 된다.

만약 열린 괄호의 내역이 없는데, 닫힌 괄호를 만난다면 ? 열린괄호가 없었으므로 닫힌 괄호는 올수없고 이는 규칙을 위반한 사례이므로 false를 반환한다.

 

그럼 열린 괄호를 어떻게 저장할 수 있을까?

 

바로 스택을 활용한다.

 

문자열 타입의 빈 스택을 생성해두고, 인자로 받은 (,)로만 이루어진 문자열 s의 첫번째 문자부터 순회한다.

문자가 열린괄호 ( 이면 스택에 넣어둔다. 그리고 ) 괄호이면, 짝을 하나 찾은 것이므로 스택에서 가장 마지막에 들어간 ( 을 빼주면 된다 = pop으로 가장 마지막 요소가 삭제된다.

그런데 여기서 주의할 점은, 스택이 만약 비어있었다면, 이전에 열린괄호 (가 없었다는 뜻이기 때문에, 규칙을 위반한 것이다. 따라서 이런 경우에는 바로 false를 리턴하도록 한다.

 

s 문자열을 다 순회하였는데, 스택이 비어있지 않다면?

스택이 비어있지 않다는 건, 이전에 들어왔던 열린 괄호 개수만큼  짝이 될 닫힌 괄호가 없었다는 뜻과 같기 때문에, 이 경우에도 false를 리턴해야 한다.

 

따라서 결과가 true가 되려면, string 순회 후에 스택이 비어있어야 함을 알 수 있다.

 

위를 바탕으로 코드를 짜면 아래와 같다.

import java.util.Stack;

class Solution {
    boolean solution(String s) {
        boolean answer = true;
        
        Stack<String> st = new Stack<>();
        
        for(int i=0; i<s.length(); i++){
            if(s.charAt(i) == '('){
                st.push("(");
            }else{
                if(st.isEmpty()){
                    return false;
                }else{
                    st.pop();
                }
            }
        }
     
        if(!st.isEmpty()) answer = false;
        
        return answer;
    }
}

 

---

<자바 문법>

** Stack을 사용하려면 java.util.Stack을 import 해야함.

** 문자열의 특정 위치의 문자에 접근하려면, s.charAt(인덱스) 를 사용하여 접근해야함.

** 문자의 경우 ' ', 문자열의 경우 " " 임을 명심하자.