#include<bits/stdc++.h>
typedef struct _XY{
int X;
int Y;
}XY;
using namespace std;
int main(void){
ios::sync_with_stdio(0);cin.tie(0);
stack<XY>S;
S.push({100000001,0});
int N,t;
cin >> N;
for(int i=1;i<=N;i++){
cin >> t;
while(S.top().X<t)
S.pop();
cout << S.top().Y << ' ';
S.push({t,i});
}
}
간단하지만 어려운 문제였다.
전에 봤던 정렬알고리즘중 하나인 중력정렬이 떠오른 문제였다.
예시를 들어 설명해보겠다.
6 9 5 7 4
뒤에서부터 살펴보면, 타워 4 는 앞에 타워7 에 레이저를 발사할 수 있고,
타워 7은 타워 9에 레이저를 발사할 수 있다. 이 때 타워 5는 무시된다.
마찬가지로 타워 5는 타워 9에 레이저를 발사할 수 있고
타워 9와 6은 발사할 수 없다. 이 때 0을 출력해야한다.
위 예시에서 6부터 4까지 입력받는데
각 구간마다 자신보다 작은 타워는 자신 뿐만 아니라 뒤에서도 볼 수 없으므로 필요없다는 사실을 알 수 있다.
스택을 이용해 불필요한 타워를 제거하며 문제를 푸는 과정은 다음과 같다.
스택에 하나씩 입력받으면서
자신보다 큰 타워가 나올 때 까지 스택을 pop 한다.
(첫 번째 입력일 경우, 앞에 타워가 없기 때문에,
높이가 최댓값+1 이고, index 가 0인 타워를 먼저 스택에 넣어
자신보다 큰 타워가 없을경우 이 타워의 인덱스인 0을 출력하게한다.)
자신보다 큰 타워가 나왔을 경우, (또는 최댓값 타워가 나왔을 경우)
그 탑의 인덱스를 출력하고 자신의 높이와 index 를 push 한다.
위 예시로 프로그램을 실행시켰을 때 각 스택상황과 출력은 다음과 같다.
max, 6 --> 자신보다 큰 타워 max 를 만났으니 max 타워의 인덱스 0 출력
max, 9 --> 자신보다 큰 타워 max 를 만날 떄 까지 pop 하고 , max 타워의 인덱스 0 출력
max, 9, 5 --> 자신보다 큰 타워를 바로 만났으니 이 타워의 인덱스 2 출력
max, 9, 7 --> 자신보다 큰 타워를 9를 만날 떄 까지 pop 하고, 그 타워의 인덱스 2 출력
max, 9, 7, 4 --> 자신보다 큰 타워 7을 만났으니 이 타워의 인덱스 4 출력