[백준] C++ 탑(2493)
서로 다른 높이를 가진 N개의 탑을 세운다.
탑에서 왼쪽 방향으로 레이저 신호를 보내는데 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다.(자신보다 높은 탑)
자신의 레이저 신호를 어떤 탑이 수신했는지 출력하는 문제이다.(수신하는 탑이 존재하지 않으면 0을 출력)
그림을 보면 첫 번째 탑은 자기보다 큰 탑이 왼쪽에 없기 때문에 0을 출력하고 두 번째 탑도 자신보다 큰 탑이 존재하지 않기 때문에 0을 출력한다. 세 번째 탑은 바로 왼쪽에 두 번째 탑의 높이가 9라서 2를 출력하고 네 번째 탑은 두 번째 탑의 높이가 더 높기 때문에 2를 출력한다. 다섯 번째 탑은 바로 왼쪽 네 번째 탑이 자신보다 높기 때문에 4를 출력한다.
이렇게 가장 먼저 만나는 탑(자신보다 높이가 높아야 함)을 찾는 문제이다.
모든 경우의 수를 계산해서 문제를 풀면 시간복잡도가 O(n^2)이 나오기 때문에 무조건 시간초과가 나올 거라고 생각했다.
그래서 나는 이 문제를 여러 가지 경우의 수로 생각을 해보았다.
처음에는 정렬을 해서 문제를 풀 수 있는가?? 에 대해서 생각을 해봤는데 답이 나오지 않았다. 두 번째에는 그러면 우선순위 큐를 사용하면 되지 않을까??라고 생각을 해보았는데 우선순위 큐도 결국 최악의 경우의 수는 O(n^2)이 되기 때문에 실패하였다. 세 번째로는 탑마다 자신보다 큰 탑의 index를 저장하면 어떨까? 생각을 해보았는데 이거 역시 최악의 경우의 수가 O(n^2)이 나온다.
결국 문제를 풀지 못하고 알고리즘 분류를 보았는데 Stack문제였다.
문제해결방법은 다음과 같다.
처음에는 6이 들어온다.
그다음은 9가 들어오는데 6은 9보다 작으면서 9보다 왼쪽에 있기 때문에 오른쪽의 있는 탑이 레이저 신호를 보내면 9에서 걸리지 6까지는 절대 오지 않는다. 그렇기에 6을 pop()해준다.
그다음으로는 5가 들어온다. 5는 9보다는 작지만 그다음으로 들어오는 수가 5보다 적을 수 있기 때문에 pop()을 해주지 않는다.(만약 5 다음에 3이 들어오면?? 3의 값을 가진 탑의 레이저 신호는 5가 받아야 한다.)
그다음으로는 7이 들어온다 7은 5보다 크기 때문에 7보다 오른쪽에 있는 탑은 적어도 7에서 걸리기 때문에(왜?? 7이 더 오른쪽에 있고 5보다 7이 크니까) 5를 pop 해주고 7을 push 한다.
마지막으로 4가 들어오는데 4는 7보다 작지만 다음으로 들어오는 수가 4보다 작을 수 있기 때문에 pop()을 해주지 않는다.
이러한 원리만 알아낸다면 어렵지 않게 문제를 해결할 수 있다.(stack에 push 할 때는 index의 정보까지 같이 넣어줘야 함.)
#include <iostream>
#include <stack>
using namespace std;
stack<pair<int,int>> s;
int result[500001];
int main(void)
{
int N = 0;
cin >> N;
for (int i = 0; i < N; i++)
{
int num = 0;
cin >> num;
if (s.empty())
{
s.push({ num,i+1 });
result[i] = 0;
}
else
{
while (true)
{
if (s.top().first < num)
{
s.pop();
if (s.empty())
{
s.push({ num,i + 1 });
result[i] = 0;
break;
}
}
else
{
result[i] = s.top().second;
s.push({ num,i+1 });
break;
}
}
}
}
for (int i = 0; i < N; i++)
{
cout << result[i] << " ";
}
return 0;
}