동블

그래프 뷰

14. 스택-괄호

4 min read

스택 - 괄호 / 단조 스택

Summary

“직전 것과 비교해 짝을 맞추거나 지운다”, “여는/닫는 구조”가 나오면 스택이다.
Java에서는 Stack 클래스가 아니라 Deque<T> st = new ArrayDeque<>();를 쓴다.

언제 쓰는가

문제 신호처리
괄호 짝 맞추기여는 건 push, 닫는 건 peek/pop
인접한 짝 제거top과 같으면 pop, 아니면 push
문자 폭발스택 또는 StringBuilder를 스택처럼 사용
수식 / 후위 표기연산자 우선순위 스택
직전보다 큰/작은 값 추적단조 스택, 인덱스 저장

Important

Queue/Stack/Deque 메서드 방향표는 문법/A_필수/ArrayDeque.md를 대표로 본다.

복잡도

작업복잡도
괄호 검증O(N)
인접 제거O(N)
단조 스택O(N)
공간O(N)

올바른 괄호 검증 템플릿

import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
 
        StringBuilder sb = new StringBuilder();
        for (int t = 0; t < n; t++) {
            String s = br.readLine();
            sb.append(isValid(s) ? "YES" : "NO").append('\n');
        }
        System.out.print(sb);
    }
 
    static boolean isValid(String s) {
        Deque<Character> st = new ArrayDeque<>();
 
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                st.push(c);
                continue;
            }
 
            if (st.isEmpty()) return false;
            char open = st.pop();
 
            if (c == ')' && open != '(') return false;
            if (c == ']' && open != '[') return false;
            if (c == '}' && open != '{') return false;
        }
 
        return st.isEmpty();
    }
}

인접 짝 제거

static String removeAdjacent(String s) {
    Deque<Character> st = new ArrayDeque<>();
 
    for (char c : s.toCharArray()) {
        if (!st.isEmpty() && st.peek() == c) {
            st.pop();
        } else {
            st.push(c);
        }
    }
 
    StringBuilder sb = new StringBuilder();
    while (!st.isEmpty()) sb.append(st.pop());
    return sb.reverse().toString();
}

push()로 앞에 넣었기 때문에 마지막에 reverse()가 필요하다.

단조 스택 - 오큰수 핵심

int[] ans = new int[n];
Arrays.fill(ans, -1);
Deque<Integer> st = new ArrayDeque<>(); // 인덱스 저장
 
for (int i = 0; i < n; i++) {
    while (!st.isEmpty() && arr[st.peek()] < arr[i]) {
        ans[st.pop()] = arr[i];
    }
    st.push(i);
}

자주 하는 실수

실수주의
닫는 괄호에서 빈 스택 확인 누락st.isEmpty() 먼저
마지막에 스택이 비었는지 확인 누락열린 괄호가 남으면 실패
인접 제거 결과를 뒤집지 않음push()는 앞에 넣으므로 reverse 필요
단조 스택에 값 저장정답 위치가 필요하면 인덱스 저장
Stack 클래스 사용Deque<T> st = new ArrayDeque<>(); 권장

엣지케이스

빈 문자열인가?
닫는 괄호로 시작하는가?
여는 괄호만 남는가?
괄호 종류가 여러 개인가?
인접 제거 후 새 인접쌍이 생기는가?
동일 값 처리에서 < 인가 <= 인가?

백지 복원

1. 괄호 검증에서 닫는 괄호를 만났을 때 순서는?
2. 인접 제거에서 push로 쌓은 결과를 왜 뒤집는가?
3. 단조 스택에서 인덱스를 저장하는 이유는?
4. Java 스택 선언은 무엇으로 통일하는가?

관련 문서