[Java] 프로그래머스(level-2) - 올바른 괄호

입출력 예시

Input-1
”()()”
Output-1
true

Input-2
)()(
Output-2
false

문제 풀이

---

이 문제의 경우 스택(Stack)으로 접근하여 푸는 것이 가장 쉽기에 스택을 활용하여 풀어보았다.
괄호만으로 이루어진 문자열을 순회하며 ”(“일 때는 스택에 “(“를 추가하고, “)”일 때는 “(“를 꺼내는 과정을 통해
스택의 empty 유무를 통해 괄호문자열을 검증할 수 있다.

한 번 코드로 작성해보자.

for(int i=0; i<s.length(); i++) {
    if(s.charAt(i) == '(') st.push(s.charAt(i));
    else if(s.charAt(i) == ')') st.pop();
}
if(!st.empty()) answer = false;

위 코드와 같이 “(“일 때는 스택에 저장하고, “)”일때는 “(“를 꺼낸다.
반복문 종료 후 스택이 비어있지 않으면 올바른 괄호문자열이 아니므로 false를 반환하면 된다.

EmptyStackException 발생

다만, 입력 괄호 문자열이 “((()))))”같이 “)”이 더 많을 경우를 생각해보자.
“(((“까지는 스택에 저장하고, “)))”까지는 스택에서 꺼내게 된다. 그런데, 두개의 “)”가 남고, 스택은 비어있는데 “(“를 꺼내라고 동작하게 되면서 EmptyStackException를 발생시키게 된다.

예외에 대해서 처리하기 위해 try catch문으로 감싸 다시 작성해보자.

try {
    for(int i=0; i<s.length(); i++) {
        if(s.charAt(i) == '(') st.push(s.charAt(i));
        else if(s.charAt(i) == ')') st.pop();
    }
    if(!st.empty()) answer = false;
}catch(EmptyStackException e) {
    answer = false;
}

예외 처리 코드를 추가하면 위 코드와 같이 작성할 수 있다.

예외처리 제거

그런데, 위 문제와 같은 상황에서 예외를 발생시키지 않는 코드를 작성할 수 없을까? 고민하게 되었다.
그렇다면 반복문을 순회하며 “)”일 경우 바로 스택에서 꺼내는 것이 아니라 스택이 비어있는지를 추가로 확인해보면 된다고 생각했다.

바로 코드로 작성해보자.

for(int i=0; i<s.length(); i++) {
    if(s.charAt(i) == '(') st.push(s.charAt(i));
    else if(s.charAt(i) == ')') {
        if(st.empty()) {
            answer = false;
            break;
        }
        else st.pop();
    }
}

위 코드를 보면 “)”일 경우의 조건에서 추가로 if else 조건문이 추가되었다.
“)”일 경우에 스택이 비어있다면 어차피 올바른 괄호문자열이 아니기에 false를 반환하고 반복문을 탈출하도록 구현하였다.

작성 코드

import java.util.*;

class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();

        long start = System.currentTimeMillis();
        solution2(s);
        long end = System.currentTimeMillis();
        System.out.println("\n수행시간 = " + (end-start));
    }

    public static boolean solution(String s) {
        boolean answer = true;
        Stack<Character> st = new Stack<>();
        try {
            for(int i=0; i<s.length(); i++) {
                if(s.charAt(i) == '(') st.push(s.charAt(i));
                else if(s.charAt(i) == ')') st.pop();
            }
            if(!st.empty()) answer = false;
        }catch(EmptyStackException e) {
            answer = false;
        }
        return answer;
    }

    public static boolean solution2(String s) {
        boolean answer = true;
        Stack<Character> st = new Stack<>();
        for(int i=0; i<s.length(); i++) {
            if(s.charAt(i) == '(') st.push(s.charAt(i));
            else if(s.charAt(i) == ')') {
                if(st.empty()) {
                    answer = false;
                    break;
                }
                else st.pop();
            }
        }
        if(!st.empty()) answer = false;
        return answer;
    }
}

회고

• 전에도 몇 번 풀어보았던 문제이기에 똑같은 풀이방식보다는 다른 접근방식을 고민할 수 있었다.
• try catch문을 통해 발생한 EmptyStackException 로 반드시 예외를 처리해야하는 상황이 아니기에 예외처리를 제거한 코드를 작성할 수 있었다.