문제 이해
백준 2493번 탑 문제는 일직선 위에 놓인 탑들이 레이저 신호를 발사할 때, 각 탑의 신호를 수신하는 탑의 번호를 찾는 문제입니다. 각 탑은 자신보다 왼쪽에 있으면서 자신보다 높은 탑 중 가장 가까운 탑에게 신호를 보냅니다.
처음 접근했던 방법과 고민들
첫 번째 고민: 어떤 정보를 저장해야 할까?
처음에는 탑의 높이만 저장하면 될 것 같았습니다. 하지만 문제를 자세히 읽어보니 탑의 번호를 출력해야 했습니다. 그래서 높이와 번호를 함께 저장해야 한다는 것을 깨달았습니다.
pair<int, int> high (0, 0); // 처음에는 단순하게 생각했었습니다두 번째 고민: 스택에 무엇을 저장할까?
손으로 그려가며 시뮬레이션해보니, 각 탑마다 높이와 번호 정보가 모두 필요하다는 것을 알았습니다. 단순히 높이만 저장해서는 몇 번 탑인지 알 수 없었기 때문입니다.
stack<pair<int, int>> S; // 높이, 번호세 번째 고민: 언제 스택에서 pop을 해야 할까?
이 부분이 가장 어려웠습니다. 처음에는 복잡하게 생각했는데, 핵심은 현재 탑보다 낮은 탑들은 더 이상 신호를 받을 수 없다는 점이었습니다.
예를 들어, 높이가 [6, 9, 5, 7, 4] 순서로 있다면:
- 7이 들어올 때, 5는 더 이상 다른 탑의 신호를 받을 수 없습니다
- 왜냐하면 5보다 오른쪽에 있는 모든 탑들은 7에게 신호를 보내거나, 7보다 높은 탑에게 신호를 보낼 것이기 때문입니다
최종 해결 과정
핵심 아이디어
- 스택에는 아직 신호를 받을 가능성이 있는 탑들만 저장합니다
- 새로운 탑이 들어올 때, 현재 탑보다 낮은 탑들은 모두 제거합니다
- 스택에서 가장 위에 있는 탑이 현재 탑의 신호를 받는 탑입니다
알고리즘 순서
- 스택에 가장 높은 가상의 탑(INT_MAX, 0)을 넣어 초기화합니다
- 각 탑에 대해:
- 현재 탑보다 낮은 탑들을 스택에서 모두 제거합니다
- 스택의 top에 있는 탑의 번호를 출력합니다
- 현재 탑을 스택에 추가합니다
최종 코드
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
stack<pair<int, int>> S; // 높이, 번호
int repeat;
cin >> repeat;
// 가장 높은 가상의 탑으로 초기화 (모든 탑이 신호를 받을 수 있도록)
S.push(make_pair(INT_MAX, 0));
for(int i = 1; i <= repeat; i++){
int in;
cin >> in;
// 현재 탑보다 낮은 탑들은 더 이상 신호를 받을 수 없으므로 제거
while(!S.empty() && S.top().first < in){
S.pop();
}
// 스택의 top이 현재 탑의 신호를 받는 탑
cout << S.top().second << " ";
// 현재 탑을 스택에 추가
S.push(make_pair(in, i));
}
return 0;
}시간 복잡도 분석
시간 복잡도: O(N)
- 각 탑은 스택에 한 번 들어가고 한 번 나옵니다
- while문이 있어서 복잡해 보이지만, 전체적으로는 각 원소가 한 번씩만 처리됩니다
공간 복잡도: O(N)
- 최악의 경우 모든 탑이 스택에 저장될 수 있습니다
배운 점들
1. 스택의 활용
스택은 단순히 LIFO 구조가 아니라, "나중에 처리될 가능성이 있는 것들"을 저장하는 용도로 활용할 수 있다는 것을 배웠습니다.
2. 불필요한 정보 제거의 중요성
현재 탑보다 낮은 탑들을 제거하는 것처럼, 앞으로 사용되지 않을 정보를 적극적으로 제거하는 것이 효율적인 알고리즘의 핵심이었습니다.
3. 경계 조건 처리
INT_MAX로 가상의 탑을 만들어 초기화하는 것처럼, 경계 조건을 미리 처리해두면 코드가 훨씬 깔끔해집니다.
마무리
이 문제를 통해 스택을 단순한 자료구조가 아닌 문제 해결 도구로 활용하는 방법을 배웠습니다. 특히 "미래에 필요한 정보만 유지하고 불필요한 정보는 제거한다"는 개념이 인상 깊었습니다. 이런 아이디어는 다른 스택 문제에서도 유용하게 활용될 것 같습니다.
