문제
https://www.acmicpc.net/problem/2493
모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다.
예를 들어 높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 수평 직선에 일렬로 서 있고, 모든 탑에서는 주어진 탑 순서의 반대 방향(왼쪽 방향)으로 동시에 레이저 신호를 발사한다고 하자. 그러면, 높이가 4인 다섯 번째 탑에서 발사한 레이저 신호는 높이가 7인 네 번째 탑이 수신을 하고, 높이가 7인 네 번째 탑의 신호는 높이가 9인 두 번째 탑이, 높이가 5인 세 번째 탑의 신호도 높이가 9인 두 번째 탑이 수신을 한다. 높이가 9인 두 번째 탑과 높이가 6인 첫 번째 탑이 보낸 레이저 신호는 어떤 탑에서도 수신을 하지 못한다.
탑들의 개수 N과 탑들의 높이가 주어질 때, 각각의 탑에서 발사한 레이저 신호를 어느 탑에서 수신하는지를 알아내는 프로그램을 작성하라.
입력
첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 이상 100,000,000 이하의 정수이다.
제한
시간제한: 1.5초
메모리 제한: 128MB
해결 방법
해당 문제를 보고 처음 든 생각은 그리디하게 풀이하는 것이었다.
그리디하게 접근하기 전 최악의 경우의 수를 계산해야한다.
계산된 최악의 경우의 수는 1, 2, 3, 4, 5 와 같이 오름차순으로 탑의 높이가 주어졌을 때이다. 이와 같은 경우 시간복잡도가 O(n^2)로 현재 n이 500, 000이기 때문에 500,000*500,000의 시간 복잡도가 계산되어 1.5초를 능가한다. <- 🙅🏻♀️
이후 DP인가 하여 알고리즘을 고려해보니 해답이 나오지 않았고 메모리 제한이 128MB인데, 탑들의 높이는 100,000,000가 최대이기 때문에 저장하는 것도 메모리 초과가 발생할 것이라고 판단하였다.
👉🏻 결국 자료구조적인 측면으로 접근하여 스택을 사용하게 되었다.
스택 사용 이점
위에서 그리디하게 접근하는 경우 최악의 경우의 수 계산에서 적합하지 않다는 판단을 하였다. 시간 복잡도적인 측면에서 계산되지 않아도 될 부분들을 계산하게 되기 때문이었다.
해당 사진에서 새롭게 추가된 파란색 탑의 수신 탑을 찾는 경우에는, 맨 처음 탑까지 방문하여 찾아야 한다 -> 이게 시간복잡도 O(n^2)의 경우이다.
🚨 이때 자료구조와 탑의 특성을 이용하여 중복을 줄여 시간복잡도에 적합한 해답을 도출할 수 있다!
그림을 통해 접근하면, 새롭게 추가된 노란색 탑의 레이저 수신 탑을 찾는 경우에는 제일 큰 것만 찾으면 이전의 것은 고려하지 않아도 된다는 것을 상기해야 한다. 이 개념을 통해서 중복을 줄일 수 있다.
어떠한 탑(i번째)의 수신탑을 찾는 경우를 고려해보자.
만약 스택에 i-1번째의 탑이 들어있는데 해당 높이는 5이다.
하지만 i번째의 수신탑의 높이는 6이다.
결과적으로, i-1번째의 탑은 i번째의 탑의 수신탑이 될 수 없다.
이에 따라 i+1번째의 수신탑을 찾는 경우 i-1은 고려될 필요가 없다. 어차피 i번째의 수신탑이 이보다 크기 때문이다.
이와 같은 개념으로, 어떠한 탑의 수신탑을 찾을 때
-
스택이 비어있는 경우.
수신탑이 없는 경우이기 때문에 0 출력. -
스택이 비어있지 않은 경우
a. 스택 최상단 탑의 높이가 현재 탑보다 작은 경우(수신탑 아님) -> pop
b. 스택 최상단 탑의 높이가 현재 탑보다 같거나 큰 경우(수신탑 찾음) -> 현재 탑 add
위와 같은 과정을 통해 중복적인 로직을 제거하며 보다 빠르게 수신탑을 찾을 수 있다. 스택은 항상 최적화된 값들을 갖게 된다는 것이 포인트이다.
코드
import java.util.*;
import java.io.*;
class Node {
int cost;
int index;
public Node(int cost, int index) {
this.cost = cost;
this.index = index;
}
}
class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
List<Node> nodes = new ArrayList<>();
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 1; i <= N; i++) {
nodes.add(new Node(Integer.parseInt(st.nextToken()), i));
}
List<Integer> answers = getResult(nodes);
StringJoiner sj = new StringJoiner(" ");
for (int answer : answers) {
sj.add(Integer.toString(answer));
}
System.out.println(sj);
}
private static List<Integer> getResult(List<Node> nodes) {
final int NON = 0;
Stack<Node> stack = new Stack<>();
List<Integer> answer = new ArrayList<>();
for (Node node : nodes) {
while(true){
if(stack.isEmpty()){
answer.add(NON);
stack.add(node);
break;
}
Node peekNode = stack.peek();
if(peekNode.cost<node.cost){
stack.pop();
} else{
stack.add(node);
answer.add(peekNode.index);
break;
}
}
}
return answer;
}
}오랜만에 알고리즘을 푸니 생각이 잘 안된다.
다시 차근차근 풀며 내실을 다져야겠다.
