[알고리즘-자바] 프로그래머스 스택/큐 < 올바른 괄호

본 글은 다크모드에 최적화되어 있습니다.

 

문제

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

프로그래머스

언어

자바 Java

로직

괄호가 올바르게 배치되어 있는지 확인하면 되는 문제입니다. 

 

스택 사용

스택에는 열린 괄호만 저장해 줍니다. 닫힌 괄호가 존재한다면 스택에서 열린 괄호를 빼주면서 최종적으로 스택의 크기가 0이 되는지 확인하기 위하여 사용합니다.

Stack<Character> stack = new Stack<>();

열린 괄호

열린괄호가 존재한다면 스택에 저장해 줍니다. 

for (int i = 0; i < brackets.length; i++) {
    char bracket = brackets[i];
    if (bracket == '(')
        stack.add(bracket);
     // ..생략
}

닫힌 괄호

닫힌 괄호가 존재한다면 스택에서 열린 괄호를 한 개 빼줍니다. 근데 여기서 스택이 비워져 있다면 괄호 배치가 옳지 않은 상황이므로 올바른 괄호가 아니게 됩니다. 따라서 이 경우에는 결과를 fasle로 반환합니다.

for (int i = 0; i < brackets.length; i++) {
    char bracket = brackets[i];
    // ..생략
    else {
        if (stack.isEmpty())
            return false;
        stack.pop();
    }
}

최종

위에서 열린-닫힌 괄호 로직을 처리하고 반복문을 종료하였을 때, 스택이 비워져 있는 상태인지 확인합니다. 스택이 비워져 있어야 열린 괄호가 들어있던 스택에서 닫힌 괄호를 만나 하나씩 꺼내면서 둘의 개수가 일치하게 되기 때문입니다.

if (stack.isEmpty())
    return true;
return false;

---

코드

import java.util.Stack;

class Solution {
    boolean solution(String s) {
        char[] brackets = s.toCharArray();
        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < brackets.length; i++) {
            char bracket = brackets[i];
            if (bracket == '(')
                stack.add(bracket);
            else {
                if (stack.isEmpty())
                    return false;
                stack.pop();
            }
        }

        if (stack.isEmpty())
            return true;
        return false;
    }
}