[문제 접근]
단순히 각 탑에서 레이저를 쐈을 때, 레이저를 쏜 방향으로 탑의 높이를 모두 확인하며 해당 레이저를 수신한 탑을 찾게 된다면 시간복잡도는 O(N*N), 즉 25*1e10이 되어 주어진 시간 제한 안에 해결할 수 없다.
문제를 다시 읽어봤을 때 탑의 높이는 왼쪽에서 순서대로 입력값이 주어지는데, 탑이 발사하는 레이저의 방향이 왼쪽이라는 점에 주목해야 한다. (입력값이 주어지는 방향과 반대)
또한 레이저 신호를 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다고 했으므로, 높이가 H인 탑에서 레이저를 발사하여 높이가 H’(H<H’)인 탑에서 신호를 수신했다고 가정해봤을 때 높이H 탑의 오른쪽에 있는 탑들은 아무리 레이저 신호를 발사해도 그 신호가 높이H 탑과 높이H’ 탑 사이의 탑들에는 도달하지 않는다는 결론에 도달하게 된다.
[필요한 자료구조]
현재 탑의 높이 H보다 이전에 입력받은 더 낮은 높이의 탑들은 이후의 탑에서 확인할 때에도 사용하지 않기 때문에 이 정보들을 지움으로써 시간복잡도를 줄일 수 있다. 이때, 레이저를 발사하는 방향이 주어지는 입력과 반대 방향임을 고려해보면 필요 없는 정보를 입력되는 반대 방향으로 지울 수 있는 자료구조로는 스택(stack)이 있다는 사실을 알 수 있다.
스택의 특징: 제일 마지막에 들어간 원소가 제일 먼저 나옴(후입선출), LIFO (Last In First Out)ex) 프링글스, 편의점 음료수, 함수 호출
[추가 point]
c++에는 <algorithm>(정확히는 <utility> 헤더가 포함된)헤더 아래에 pair이라는 STL이 존재하는데, 이 pair 클래스를 활용하여 서로 연관된 2개의 데이터를 한 쌍으로 묶어서 다룰 수 있다. 이때, 구조체를 따로 정의하지 않아도 된다는 편리함이 있으나 pair의 first와 second 데이터가 각각 어떤 데이터인지 헷갈릴 수 있으니 꼭 주의하자.
또, 발사된 레이저 신호를 받지 못하는 경우에 대한 예외처리도 꼼꼼하게 체크해주자.
→ 이 경우에 스택이 비게 될 것임 (현재 탑의 높이보다 낮으면 모두 pop해줬기 때문)
[전체 코드]
#include <iostream>
#include <stack>
#include <algorithm>
#define FASTIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
using namespace std;
typedef pair<int,int> pii;
int N,H;
stack<pii> s; // first: 탑의 높이, second: 탑의 인덱스
int main() {
FASTIO;
cin >> N;
for(int i=1; i<=N; i++) {
cin >> H;
while(!s.empty()) {
if(H < s.top().first) { // 서로 다른 탑의 높이
cout << s.top().second << ' ';
break;
}
s.pop();
}
if(s.empty()) cout << "0 ";
s.push({H,i});
}
}
C++
복사
