- 문제 : https://www.acmicpc.net/problem/2493
- 풀이 : https://github.com/kyukong/Algorithm/tree/main/백준/Gold/2493. 탑
- 참고 사이트 : https://steady-coding.tistory.com/15
다양한 높이의 탑 리스트가 있다.
탑에서 왼쪽 방향으로 레이저 신호를 보낼 때, 수신하는 탑의 위치 목록을 출력한다.
가장 먼저 닿게되는 높은 탑의 위치를 출력하면 된다.
처음에는 이중 for 문을 이용하였지만 시간 초과가 발생하였다.
import java.io.*;
import java.util.*;
public class Main {
private static int n;
private static int[] tops;
private static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
tops = new int[n];
for (int i = 0; i < n; i++) {
tops[i] = Integer.parseInt(st.nextToken());
}
int accept;
for (int now = 0; now < n; now++) {
accept = 0;
for (int next = now - 1; next >= 0; next--) {
if (tops[now] >= tops[next]) {
continue;
}
accept = next + 1;
break;
}
sb.append(accept).append(" ");
}
System.out.println(sb);
}
}문제에서 주어진 조건의 N 은 500,000 으로 매우 큰 편이다.
시간 복잡도를 줄이기 위해 Stack 자료구조를 이용하였다. (참고 사이트)
왜 Stack 자료구조를 사용했는가?
가장 먼저 닿는 탑의 위치를 구하기 위해서는 왼쪽에 있는 탑들의 높이 정보가 필요하다.
하지만 모든 탑의 높이 정보를 알고 있을 필요는 없다. (현재의 탑의 높이보다 작을 경우에는 필요 없다.)
입력을 받는 것과 동시에 이전 이력들을 관리해야 했으며, 현재보다 높이가 작은 탑을 쉽게 제거하며 관리하기 위해 Stack 자료구조를 사용하였다.
-
Stack 이 비어있는 경우
문제 조건 중에서 ‘레이저 신호를 수신하는 탑이 존재하지 않으면 0을 출력’ 이 있으므로 0을 출력한다.
-
Stack 에 값이 존재하는 경우
-
왼쪽의(Stack 상단의) 탑이 현재 탑의 높이보다 큰 경우
바로 레이저가 닿는 탑을 찾았다. 해당 값을 출력한다.
또한 이후의 탑들의 높이를 알 수 없으며 현재의 탑보다 높이가 작을 경우 현재의 탑에 닿을 가능성이 있기 때문에 현재 탑의 정보를 Stack 에 저장한다.
-
왼쪽의 탑이 현재 탑의 높이보다 작거나 같은 경우
문제에 ‘탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치’ 되어있다고 했으므로 높이가 같은 경우에는 수신하지 못한다고 판단하였다.
왼쪽의 탑이 현재보다 작거나 같은 경우 이후에 검증하게 될 오른쪽의 탑들은 현재 위치의 왼쪽(가장 상단)의 탑에 닿을 가능성이 전혀 없어 Stack 에서 제거한다.
즉, 왼쪽의 탑들이 현재보다 작은 경우 전혀 도달하지 못하기 때문에 높이가 큰 탑을 만날때까지 모두 제거한다.
제거하는 과정에서 Stack 이 비게되는 경우 0 을 출력한다.
제거하는 과정에서 현재보다 큰 높이의 탑을 마주할 경우 큰 높이의 탑 정보를 출력하고 현재 탑의 정보를 Stack 에 저장한다.
-
import java.io.*;
import java.util.*;
public class Main {
private static int n;
private static Stack<Top> stack = new Stack<>();
private static StringBuilder sb = new StringBuilder();
// Stack 에 현재 높이와 위치 정보를 모두 담기 위해 객체를 생성하였다.
private static class Top {
int height;
int num;
public Top(int height, int num) {
this.height = height;
this.num = num;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
int nowHeight;
Top prior;
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
nowHeight = Integer.parseInt(st.nextToken());
if (stack.empty()) {
stack.push(new Top(nowHeight, i + 1));
sb.append(0).append(" ");
continue;
}
prior = stack.peek();
if (prior.height > nowHeight) {
stack.push(new Top(nowHeight, i + 1));
sb.append(prior.num).append(" ");
} else {
while (true) {
if (stack.empty()) {
stack.push(new Top(nowHeight, i + 1));
sb.append(0).append(" ");
break;
}
prior = stack.peek();
if (prior.height > nowHeight) {
stack.push(new Top(nowHeight, i + 1));
sb.append(prior.num).append(" ");
break;
}
stack.pop();
}
}
}
System.out.println(sb);
}
}