프로그래머스 올바른 괄호 JAVA 풀이 (스택)

🔗 문제 링크

프로그래머스

---

📌 문제 개요

괄호 문자열이 주어졌을 때 올바른 괄호인지 판별하는 문제이다.

올바른 괄호란 열린 괄호 ( 가 나오면 반드시 대응되는 닫힌 괄호 ) 가 존재해야 하며, 순서 또한 올바르게 짝지어져 있어야 한다.

예를 들어

• ()() → 올바른 괄호
• (())() → 올바른 괄호
• )()( → 올바르지 않은 괄호
• (()( → 올바르지 않은 괄호

문자열이 올바른 괄호이면 true, 아니면 false를 반환한다.

---

📌 접근 방법

괄호의 짝을 확인해야 하므로 스택(Stack)을 사용한다.

문자를 하나씩 확인하면서

• ( 이면 스택에 저장한다.
• ) 이면 가장 최근에 저장된 ( 와 짝을 맞춘다.

만약 ) 를 만났는데 스택이 비어 있다면 짝이 맞는 ( 가 없는 것이므로 즉시 false를 반환한다.

모든 문자를 확인한 뒤에도 스택에 ( 가 남아 있다면 짝이 맞지 않은 괄호가 존재하는 것이므로 false를 반환한다.

---

📌 핵심 아이디어

1. 열린 괄호는 스택에 저장

열린 괄호가 나오면 나중에 닫힌 괄호와 짝을 맞추기 위해 스택에 저장한다.

if(ch == '('){
    stack.push(ch);
}

---

2. 닫힌 괄호가 나오면 짝 확인

스택이 비어있다는 것은 짝이 되는 ( 가 없다는 의미이다.

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

예시 : 첫 문자부터 짝이 맞지 않으므로 바로 false를 반환한다.

)()(
^

---

3. 짝이 존재하면 제거

가장 최근의 ( 와 현재 ) 를 하나의 쌍으로 처리한다.

stack.pop();

 

예시

(())

과정

( -> push
( -> push
) -> pop
) -> pop

 

최종적으로 스택이 비게 된다.

---

4. 모든 순회 후 스택 확인

return stack.isEmpty();

예시

(()(

과정

( -> push
( -> push
) -> pop
( -> push

최종 스택 : 스택이 비어있지 않으므로 false를 반환한다.

[(, (]

---

📌 전체 코드

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    boolean solution(String s) {
        Deque<Character> stack = new ArrayDeque<>();

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

            if(ch == '('){
                stack.push(ch);
            } else {
                if(stack.isEmpty()){
                    return false;
                }
                stack.pop();
            }
        }

        return stack.isEmpty();
    }
}

 

---

📄 정리

• 괄호의 짝을 확인하는 대표적인 스택 문제이다.
• ( 는 push, ) 는 pop으로 처리한다.
• ) 를 만났는데 스택이 비어있으면 즉시 false를 반환한다.
• 순회가 끝난 뒤 스택이 비어있어야 올바른 괄호이다.
• 괄호 종류가 하나뿐이라 카운터 변수만으로도 해결 가능하지만, 스택 풀이가 직관적이고 확장성이 좋다.