문제 요약
높이가 다른 탑들이 배열로 주어진다.
하나의 탑은 본인을 기준으로 왼쪽으로 레이저를 발사한다.
이 때 레이저가 몇 번째 탑에 전달되는지 구한다.
입력조건
첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 이상 100,000,000 이하의 정수이다.
정답 도출 과정
(1) 하나의 탑을 기준으로 왼쪽에서 본인보다 높지만 가장 가까운 탑을 찾아야 한다.
문제에서 해결하고자하는 가장 기본이 되는 요구이다.
이전에 더 높은 탑이 있었는지, 아닌지는 알 필요 없으며 현재보다 높으면서도 가까운 탑을 찾아야 한다.
(2) 판단하고자 하는 탑을 기준으로 가장 최신의 이전 탑부터 비교할 수 있어야 한다
위 (1)번의 요구사항을 해결하기 위함이다. 최신의 탑부터 비교해가며 현재 탑보다 더 높은가?를 계속 비교하여 존재하는 경우 정답이 되고 존재하지 않는다면 모든 이전의 탑들보다 가장 높은 탑이 된다.(신호가 어떤 탑에도 전달되지 않음 0)
정답을 도출한 후 다음 탑을 위해 현재 탑이 가장 최신의 탑으로써 비교될 수 있게끔 해야한다.
따라서 stack 자료구조를 사용하였다.
(3) 우측의 탑들은 좌측 탑들의 모든 히스토리를 알 필요 없다.
새로운 탑 입장에서 가장 최신의 탑들은 가장 높았던 최근의 탑 또는 가장 높았던 최근의 탑에 신호를 전달할 수 있었던 탑일 것이다.
이들보다 낮은 탑이라면 가장 최근의 탑에 신호를 전달할 수 있고 이들보다 크다면 그 어디에도 신호를 전달할 수 없다.
검은색의 경우 이미 사전에 비교되어 pop된 탑들이고 파란색이 현재 비교를 진행하는 탑이다.
과거의 탑(검은색)들이 얼마나 높고 낮았던 간에 절대로 해당 탑에 신호를 전달할 수 없다.
위의 경우라면 파란색 탑이 가장 최신 탑보다 높기 때문에 해당 탑을 배제하고 3번째 탑에 신호를 전달하게 될 것이다.
이런 방식으로 비교를 수행했던 탑을 최신 탑으로 갱신하고 과거의 탑들을 pop하는 과정을 반복하면 된다.
풀이코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
bufferedReader.readLine();
int[] arr = Arrays.stream(bufferedReader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
Deque<Top> deque = new ArrayDeque<>();
int[] answers = new int[arr.length];
deque.offerLast(new Top(0, arr[0]));
for (int i = 1; i < arr.length; i++) {
while (!deque.isEmpty()) {
if (arr[i] < deque.peekLast().num) {
answers[i] = deque.peekLast().idx + 1;
break;
}
deque.pollLast();
}
deque.offerLast(new Top(i, arr[i]));
}
StringBuilder stringBuilder = new StringBuilder();
for (int answer : answers) {
stringBuilder.append(answer).append(" ");
}
System.out.println(stringBuilder);
}
static class Top {
int idx;
int num;
public Top(int idx, int num) {
this.idx = idx;
this.num = num;
}
}
}탑의 위치 정보를 기록하기 위해 Top 클래스를 만들고 스택 자료구조에 활용했다.
최악의 경우 50만개의 케이스가 주어지고 1.5초의 시간이 주어지기 때문에 단순 반복을 통해 찾는 방법(O(N^2)으로는 해결이 안되며
해당 방법을 통해 O(N)+ 시간복잡도로 해결할 수 있다.
