[Algorithm: 스택/큐] 프로그래머스 <올바른 괄호>

Stack Java Programmers Lv.2

문제

 

https://school.programmers.co.kr/learn/courses/30/lessons/12909?language=java

프로그래머스

 

 

문제 설명

주어진 문자열 s가 (와 )로만 이루어져 있을 때, 올바른 괄호 문자열인지 판별하는 문제다.

올바른 괄호란 모든 여는 괄호에 대응하는 닫는 괄호가 존재하고, 괄호가 올바른 순서로 닫혀야 한다.

• ()() true
• (()) true
• )(() false
• (() false

 

 

처음 접근

처음엔 카운터 하나로 풀 수 있지 않을까 생각했다. (를 만나면 +1, )를 만나면 -1 해서 마지막에 0이면 올바른 괄호라는 방식이다.

하지만 이 방법은 순서 문제를 잡지 못한다.
예를 들어 )(는 카운터가 최종적으로 0이 되지만 올바른 괄호가 아니다.
카운터가 음수가 되는 순간을 체크해야 하는데, 그렇게 되면 결국 스택과 동일한 로직이 된다.

 

 

핵심 아이디어

이 문제의 핵심은 가장 최근에 열린 괄호와 현재 닫는 괄호가 짝을 이루는지 확인하는 것이다.

"가장 최근에 넣은 것을 가장 먼저 꺼낸다" 이건 정확히 스택(LIFO)의 특성이다.

여는 괄호 (를 만나면 스택에 push, 닫는 괄호 )를 만나면 스택에서 pop.
짝이 맞지 않으면 스택이 비었거나, 끝났는데 스택에 원소가 남아있다.

 

 

스택 동작 시각화

세 가지 케이스를 직접 추적해보자.

CASE 1 — "(())" → true

문자열 ( ( ) )

① ( push(

② ( push((

③ ) pop(

④ ) pop

스택 비었음 → true

CASE 2 — ")(" → false (닫는 괄호가 먼저 나옴)

문자열 ) (

① ) 확인 ← 스택이 비어있음!

isEmpty → false 즉시 반환

CASE 3 — "(()" → false (여는 괄호가 남음)

순회 후( ← 스택에 ( 남음

!isEmpty → false

 

예외 케이스 정리

이 문제에서 false가 되는 경우는 딱 두 가지다.

1

)를 만났는데 스택이 비어있다 → 짝 없는 닫는 괄호

2

순회가 끝났는데 스택에 (가 남아있다 → 짝 없는 여는 괄호

 

---

 

최종 코드

import java.util.*;

class Solution {
    boolean solution(String s) {
        boolean answer = true;
        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            if (c == '(') {
                stack.push(c);          // 여는 괄호 → push
            } else {
                if (stack.isEmpty()) {
                    answer = false;   // 예외 1: 짝 없는 닫는 괄호
                } else {
                    stack.pop();        // 짝을 소비
                }
            }
        }

        if (!stack.isEmpty()) {
            answer = false;          // 예외 2: 남아있는 여는 괄호
        }

        return answer;
    }
}

 

---

 

정리

Stack

LIFO 구조로 가장 최근 여는 괄호와 짝 확인

isEmpty

닫는 괄호 도달 시 스택이 비었는지 반드시 체크

순회 후

스택에 원소가 남아있으면 짝 없는 여는 괄호 존재

괄호 문제의 핵심은 "가장 최근에 열린 것이 가장 먼저 닫혀야 한다"는 규칙이다.
이 순서 관계를 다루는 자료구조가 스택이기 때문에, 괄호 유효성 검사 유형은 스택으로 푸는 것이 정석이다.

 

* 이 포스팅은 Claude AI의 도움을 받아서 작성되었습니다.