[백준 1874] 스택 수열 (Java) - LIFO 원리 정복하기

🚀 문제 핵심 파악

1부터 $n$까지의 숫자를 스택에 넣었다 빼며 특정 수열을 만들 수 있는지 묻는 문제입니다. 여기서 핵심은 두 가지 제약 조건입니다.

1. 오름차순 Push: 스택에 넣는 숫자는 반드시 1부터 순서대로 커져야 합니다.
2. LIFO(Last In First Out): 나중에 들어간 숫자가 먼저 나와야 하므로, 현재 뽑아야 할 숫자($target$)가 스택의 최상단($top$)에 없다면 그 수열은 성립할 수 없습니다.

---

💡 해결 전략: 오름차순 포인터 제어

단순히 모든 숫자를 넣고 보는 것이 아니라, '다음에 넣어야 할 숫자'를 관리하는 포인터(nextNum)를 두는 것이 효율적입니다.

1. Push (채우기): 현재 수열에서 요구하는 숫자(target)가 아직 스택에 들어오지 않았다면, nextNum이 target과 같아질 때까지 스택에 push하고 +를 기록합니다.
2. Check (검증): 스택의 맨 위(peek)를 확인합니다.

• 만약 peek 값이 target과 다르다면? 이미 스택 아래쪽에 깔려 있거나 더 큰 숫자가 가로막고 있다는 뜻입니다. 스택 구조상 이를 건너뛰고 꺼낼 방법이 없으므로 즉시 "NO"를 출력하고 종료합니다.

3. Pop (비우기): peek 값이 target과 일치한다면 pop을 수행하고 -를 기록합니다.

---

💻 구현 코드 (Java)

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // BufferedReader와 BufferedWriter를 사용하여 입출력 최적화
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
             BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
            
            int n = Integer.parseInt(br.readLine());
            Deque<Integer> stack = new ArrayDeque<>();
            StringBuilder sb = new StringBuilder();
            
            int nextNum = 1; // 다음에 push할 오름차순 숫자 관리

            for (int i = 0; i < n; i++) {
                int target = Integer.parseInt(br.readLine());

                // 1. 타겟 숫자에 도달할 때까지 오름차순으로 push
                while (nextNum <= target) {
                    stack.push(nextNum++);
                    sb.append("+\n");
                }

                // 2. 스택의 top이 타겟과 다르다면 생성 불가능한 수열 (LIFO 제약)
                if (stack.isEmpty() || stack.peek() != target) {
                    System.out.println("NO");
                    return;
                }

                // 3. 타겟 숫자와 일치하면 pop 수행
                stack.pop();
                sb.append("-\n");
            }

            // 모든 수열이 정상적으로 생성된 경우 결과 출력
            bw.write(sb.toString());
        }
    }
}

---

🧐 기술적 고찰

• ArrayDeque의 선택: Java의 Stack 클래스는 멀티스레드 환경을 고려한 동기화 오버헤드가 있습니다. 알고리즘 풀이와 같은 단일 스레드 환경에서는 ArrayDeque를 사용해 성능을 높이는 것이 유리합니다.
• 출력 최적화: 매번 +, -를 출력하면 빈번한 I/O 호출로 인해 시간 초과가 발생할 수 있습니다. StringBuilder에 결과를 모았다가 마지막에 한 번에 출력하거나 BufferedWriter를 활용하는 것이 안전합니다.
• 시간 복잡도: 각 숫자는 스택에 정확히 한 번 들어갔다가 한 번 나옵니다. 따라서 전체 로직은 $O(N)$의 선형 시간 복잡도를 가집니다.

---

🎯 마치며

이번 문제는 스택의 가장 기본적인 동작 원리를 묻고 있지만, 문제의 조건을 코드로 구현할 때 '불가능한 지점을 어떻게 판별할 것인가'에 대한 논리적 사고를 연습하기 좋은 문제였습니다. 자료구조의 특성이 곧 알고리즘의 핵심이 된다는 것을 다시 한번 체감할 수 있었습니다.