문제
N개의 탑이 왼쪽부터 차례대로 서 있고, 각 탑은 레이저를 왼쪽 방향으로 발사한다. 레이저는 먼저 만나는 더 높은 탑이 수신한다. 각 탑에서 발사된 레이저를 어느 탑이 수신하는지 출력하는 문제이다. 수신하는 탑이 없으면 0을 출력한다.
입력
- 첫째 줄: 탑의 수 N (1 이상 500,000 이하)
- 둘째 줄: N개의 탑 높이 (1 이상 100,000,000 이하 정수)
출력
- N개의 수신 탑 번호 (공백으로 구분)
예제
| 입력 | 출력 |
|---|---|
5 6 9 5 7 4 | 0 0 2 2 4 |
풀이
스택을 이용하여 각 탑의 레이저를 수신하는 탑을 O(N)에 찾는다. 스택에는 (탑 번호, 높이) 쌍을 저장하고, 현재 탑보다 낮은 탑들은 pop한다.
- 왼쪽부터 탑을 순서대로 처리한다.
- 스택이 비어 있으면 레이저를 수신하는 탑이 없으므로 0을 출력하고, 현재 탑을 스택에 push한다.
- 스택이 비어 있지 않으면 스택 상단의 높이와 현재 탑 높이를 비교한다.
- 스택 상단 높이가 현재 탑보다 크면 그 탑이 레이저를 수신하므로 스택 상단의 번호를 출력한다.
- 스택 상단 높이가 현재 탑보다 작거나 같으면 pop하고 다시 비교를 반복한다.
핵심 아이디어: 스택을 단조 감소 스택(monotonic decreasing stack)으로 유지하면, 현재 탑의 레이저가 닿는 첫 번째 높은 탑을 O(1) 비교로 찾을 수 있다. 각 탑은 한 번 push, 한 번 pop되므로 전체 시간 복잡도는 O(N)이다.
코드
package com.ssafy.an.day149;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
public class Day111BOJ2493탑스택 { // 2493 탑 스택
static class Tow { int n, t; Tow(int n, int t) { this.n = n; this.t = t; } }
static int N;
static Stack<Tow> stack;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
N = Integer.parseInt(br.readLine());
stack = new Stack<>();
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 1; i < N + 1; i++) {
int t = Integer.parseInt(st.nextToken());
if (stack.isEmpty()) {
sb.append(stack.size()).append(" ");
stack.push(new Tow(i, t));
continue;
}
while (true) {
if (stack.isEmpty()) {
sb.append(stack.size()).append(" ");
stack.push(new Tow(i, t));
break;
}
if (stack.peek().t > t) {
sb.append(stack.peek().n).append(" ");
stack.push(new Tow(i, t));
break;
} else {
stack.pop();
}
}
}
System.out.println(sb);
br.close();
}
}복잡도
- 시간: O(N) — 각 탑은 push/pop 각 1회
- 공간: O(N)