[프로그래머스 Level 2] 올바른 괄호

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12909

프로그래머스

 

 

풀이

• 올바른 괄호는 반드시 '(' 문자로 열려서 ')' 문자로 닫혀야 한다.
• 즉, "()()" 또는 "(())()"는 올바른 괄호, ")()(" 또는 "(()(" 는 올바르지 않은 괄호이다.
• 문자열 s는 괄호로만 이루어져 있다.

 

괄호는 반드시 '('와 ')'이 쌍을 이루어야 하기 때문에 LIFO ( Last In First Out ) 자료구조인 Stack을 사용해야 한다.

여는 괄호가 나오면 무조건 Stack에 저장하고, 닫는 괄호를 만났을 때 Stack에서 괄호를 삭제한다.

만약 Stack에 여는 괄호가 존재하지 않는데 닫힌 괄호가 등장한 경우, 올바르지 않는 괄호가 된다.

 

if(array[i] == '(') {
	stack.push('(');
}

else {
    if(stack.isEmpty()){
        answer = false;
        break;
    }
    stack.pop();
}

 

그리고 문자열의 모든 괄호를 탐색한 후에도 Stack에 여는 괄호가 남은 경우도 마찬가지로 올바르지 않는 괄호이다.

 

if(!stack.isEmpty()){
    answer = false;
}

 

 

즉, 올바르지 않은 괄호가 되는 두가지 경우가 존재한다.

• Stack에 여는 괄호가 없는데 닫힌 괄호가 등장한 경우
• Stack에 여는 괄호가 남은 경우

 

전체 코드 (Java)

import java.util.*;

class Solution {
    boolean solution(String s) {
        boolean answer = true;
        Stack<Character> stack = new Stack<>();
        char[] array = s.toCharArray();
        // System.out.println(Arrays.toString(array));

        for(int i = 0; i < array.length; i++){
            // 여는 괄호가 나오면 스택에 저장
            if(array[i] == '(') {
                stack.push('(');
            }

            // 닫는 괄호가 나오면 여는 괄호를 스택에서 꺼낸다
            else {
                // 이때 여는 괄호가 없다면 잘못된 괄호이다.
                if(stack.isEmpty()){
                    answer = false;
                    break;
                }
                stack.pop();
            }
        }

        // 스택에 여는 괄호가 남은 경우 잘못된 괄호이다.
        if(!stack.isEmpty()){
            answer = false;
        }

        return answer;
    }
}

 

 

후기

괄호와 Stack의 성질의 공통점을 찾는다면 쉽게 해결할 수 있는 문제였다.