[BaekJoon] 2493번 - 탑 [Java][C++]

문제 링크

---

1. 아이디어

탑의 레이저 신호는 탑의 꼭대기에서 왼쪽 방향으로 발사되며 이를 가장 먼저 수신하는 탑을 찾아야 하는 문제다. 간단하게는 각 탑에 왼쪽 방향으로 자신보다 큰 탑이 나올 때까지 탐색하면 되지만 탑이 최대 500,000개가 주어져서 O(N²)의 시간 복잡도로는 해결할 수 없다.

포인트는 각 탑은 자신보다 큰 탑이 오른쪽에 등장하는 순간 더 이상 레이저 신호를 수신받을 수 없다는 것으로 단조 스택을 활용하면 해결할 수 있다. 왼쪽부터 오른쪽으로 각 탑을 순회하며 탑의 높이와 위치를 스택에 담는데, 이때 현재 탑이 스택의 top에 위치한 탑보다 높다면 top에 위치한 탑은 더 이상 레이저 신호를 수신받을 수 없으므로 스택에서 제거하는 과정을 반복한다. 스택이 비었다면 해당 탑이 자신보다 왼쪽의 모든 탑보다 높은 탑인 것이므로 레이저 신호를 수신하는 탑이 없게 되며, 스택이 비지 않는다면 top에 위치한 탑은 자신보다 왼쪽에 있는 높은 탑이면서 왼쪽에서 오른쪽 방향으로 스택에 탑을 담기에 가장 가까이 있는 탑이 된다.

스택에 삽입은 항상 top 보다 작은 수를 삽입하므로 이 스택은 단조 감소 스택이 된다.

---

2. 코드

1. 풀이 [Java]

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());

        Deque<int[]> stack = new ArrayDeque<>();

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            int x = Integer.parseInt(st.nextToken());

            while (!stack.isEmpty() && stack.peek()[0] < x) {
                stack.pop();
            }

            sb.append(stack.isEmpty() ? 0 : stack.peek()[1]).append(" ");
            stack.push(new int[]{x, i});
        }

        System.out.println(sb);
    }
}

2. 풀이 [C++]

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    stack<pair<int, int>> st;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;

        while (!st.empty() && st.top().first < x) {
            st.pop();
        }

        cout << (st.empty() ? 0 : st.top().second) << ' ';
        st.push({x, i});
    }
}

---

3. 디버깅

없음.

---

4. 참고

없음.

---