입력
- 첫 줄: 탑의 개수 N N (1 ≤ N N ≤ 500,000)
- 둘째 줄: N N 개의 탑 높이 (1 ≤ 높이 ≤ 100,000,000), 공백으로 구분
- 높이는 모두 서로 다름 (문제 조건)
출력
- 각 탑에서 발사된 레이저를 수신한 탑의 번호를 공백으로 구분해 출력
- 수신 탑이 없으면 0
https://www.acmicpc.net/problem/2493
해결 아이디어
이 문제는 스택을 사용하면 효율적으로 해결할 수 있습니다. 스택을 사용하기전 단순하게 접근을 했을떄, 직관적인 해결법은 왼쪽으로 모든 이전 탑을 확인하며, 자신보다 높은 첫 번째 탑을 찾는 것입니다.
- 예: 5번 탑(높이 4)의 경우, 4번(7), 3번(5), 2번(9), 1번(6)을 순서대로 확인.
- 4번 탑(높이 7)이 높이 4보다 크므로 여기서 수신.
위 내용이 이해가 되셨다면 이 문제가 왜 완전 탐색이 비효율적인지 알아봅시다
- N=500,000 N = 500,000 일 때, 500,000×500,000≈250,000,000,000 500,000 \ times 500,000 \approx 250,000,000,000 연산.
- 이는 일반적인 시간 제한(1~2초) 내에 처리하기 어렵습니다. 즉 따라서 더 효율적인 방법을 찾아야 합니다.
완전탐색이 비효율적인것은 확인했습니다. 그렇다면 스택은 왜 적합할까요 ? 문제 분석을 정확히 했다면 우리는 이전 탑들 중 더 높은 탑만 유지하면 됩니다. 스택은 가장 최근의 데이터를 빠르게 접근하고, 불필요한 데이터를 제거하는 데 최적입니다.
- 스택에 탑의 높이와 인덱스를 저장.
- 새 탑을 처리할 때, 스택의 top 탑이 현재 탑보다 낮으면 pop (이 탑은 더 이상 필요 없음).
- 스택의 top 탑이 현재 탑의 레이저를 수신.
- 현재 탑을 스택에 push.
이 패턴을 이해했을경우 왜 낮은 탑을 스택에서 제거하나? 라고 질문이 나올수있습니다. 만약 스택의 top 탑이 현재 탑보다 낮다면, 이후 탑들의 레이저는 현재 탑에서 먼저 수신되거나, 더 높은 탑을 찾을 것이므로 그 탑은 더 이상 필요 없습니다.
- 예: 높이 [6, 9, 5]에서, 3번 탑(높이 5)을 처리할 때 2번 탑(높이 9)이 스택에 있으면 1번 탑(높이 6)은 제거됨. 이유는 2번 탑이 더 가까우면서도 높기 때문입니다.
시간 복잡도는 최대 한번 push 되고 최대 한 번.pop 됩니다. 따라서 O(N) 압나다
코드를 보시면 아시겠지만 레이저는 왼쪽 방향으로 나아가는데 왜 정방향으로 탐색하나? 라고 생각될수있습니다.
문제는 탑을 왼쪽부터 오른쪽으로 번호를 매기고, 레이저도 왼쪽으로 발사됩니다. 정방향(1번 탑부터)으로 탐색하면, 스택에 이전 탑들을 순서대로 쌓고, 필요 없는 탑을 제거하며 자연스럽게 수신 탑을 찾을 수 있습니다. 역순 탐색도 가능하지만, 정방향이 문제의 흐름과 더 직관적이고 가독성이 좋습니다.
import java.io.*;
import java.util.*;
public class Main {
static BufferedReader br;
static int[] towerHeights;
static class Tower {
int index;
int height;
public Tower(int index, int height) {
this.index = index;
this.height = height;
}
}
static void input() {
try {
// 배포용 표준 입력
br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine().trim());
towerHeights = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine().trim());
for (int i = 0; i < n; i++) {
int height = Integer.parseInt(st.nextToken());
towerHeights[i] = height;
}
} catch (IOException e) {
System.err.println("입력 오류: " + e.getMessage());
}
}
static int[] solve() {
int n = towerHeights.length;
int[] receivers = new int[n];
Stack<Tower> stack = new Stack<>();
for (int i = 0; i < n; i++) {
// 현재 탑보다 높이가 낮은 탑은 스택에서 제거
while (!stack.isEmpty() && stack.peek().height <= towerHeights[i]) {
stack.pop();
}
// 스택이 비어 있으면 수신 탑 없음(0), 아니면 스택의 top 탑이 수신 탑
receivers[i] = stack.isEmpty() ? 0 : stack.peek().index;
// 현재 탑을 스택에 추가 (1-based 인덱스)
stack.push(new Tower(i + 1, towerHeights[i]));
}
return receivers;
}
public static void main(String[] args) {
input();
int[] receivers = solve();
// StringBuilder로 출력 최적화
StringBuilder sb = new StringBuilder();
for (int receiver : receivers) {
sb.append(receiver).append(" ");
}
System.out.println(sb.toString().trim());
}
}
'알고리즘 > 백준' 카테고리의 다른 글
[BoJ] - 10799번 쇠막대기 (0) | 2025.05.29 |
---|---|
[BoJ] - 2504번 괄호의 값 (0) | 2025.05.29 |
[BoJ] - 1043번 거짓말 (2) | 2023.12.12 |
[BoJ] - 2630번 색종이 만들기 (2) | 2023.12.04 |
[BoJ] - 1015번 수열 정렬 (0) | 2023.10.22 |