1. 관련 문제 🎯
문제 : 백준 2493번 탑 🏰
난이도 : 골드 5
1-1. 문제 설명 (진한 부분만 읽으면 된다.) 💬
KOI 통신연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위한 실험을 하고 있다. 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다.
- 문제 핵심
1) 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세운다. ➡️
2) 레이저 송신기는 수평 직선의 왼쪽 방향으로 발사한다. ⬅️
3) 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다.
정리해보면, 레이저 송신기는 수평 직선의 왼쪽 방향으로 발사되므로 자신보다 왼쪽에 있는 탑(자신보다 먼저 세워진 탑) 중에 자신보다 높이가 높고 자신과 거리가 가장 짧은 탑과 수신이 가능하다!
즉, 나중에 들어온 데이터가 먼저 들어온 데이터를 자신과 가까운 순서대로 살펴보는 자료 구조를 사용해야 한다.
따라서 자료 구조들 중에서 LIFO(Last In First Out)인 Stack을 사용하여 구해야 한다.
스택(Stack)의 특징
1) LIFO 구조이다.
- 위의 그림을 보면 블록마다 작성된 번호는 들어간 순서(탑의 번호)라고 가정하자!
그러면, stack에서 가장 마지막인 5번을 빼고 나머지 stack에 남은 번호들과 비교해보면, 첫번째로 stack에 남은 번호들은 자신보다 왼쪽에 있는 탑의 번호임을 확인할 수 있다. 두 번째로 알 수 있는 점은 stack의 가장 top은 4번으로 5번과 가장 가까운 번호임을 알 수 있다. 그리고 top에 가까울수록 5번과 가까운 번호이다.
1-2. 문제 예시 👩🏫
높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 수평 직선에 일렬로 서 있고, 모든 탑에서는 주어진 탑 순서의 반대 방향(왼쪽 방향)으로 동시에 레이저 신호를 발사한다고 하자. 그러면, 높이가 4인 다섯 번째 탑에서 발사한 레이저 신호는 높이가 7인 네 번째 탑이 수신을 하고, 높이가 7인 네 번째 탑의 신호는 높이가 9인 두 번째 탑이, 높이가 5인 세 번째 탑의 신호도 높이가 9인 두 번째 탑이 수신을 한다. 높이가 9인 두 번째 탑과 높이가 6인 첫 번째 탑이 보낸 레이저 신호는 어떤 탑에서도 수신을 하지 못한다.
1-3. 문제에서 구해야 하는 것 🔎
탑들의 개수 N과 탑들의 높이가 주어질 때, 각각의 탑에서 발사한 레이저 신호를 어느 탑에서 수신하는지를 알아내는 프로그램을 작성하라.
이때, 왼쪽부터 탑의 번호는 1번으로 시작하며, 수신하는 탑의 번호를 순서대로 출력해야 한다.
1-4. 입력 📩
첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 이상 100,000,000 이하의 정수이다.
N의 크기가 500,000 이하이므로 제한시간은 1.5초이다.
따라서, N^2는 최대 250,000,000,000이므로 1.5초를 넘으므로 N을 사용하여 이중 for문을 하면 제한 시간을 넘게 된다.
- stack을 사용하여 뒤에서부터 하나씩 자신의 높이보다 높은 탑을 찾는 방식은 알고리즘을 생각하기에는 단순하지만 제한 시간을 넘어서 정답이 될 수 없다.
< 이중 포문을 사용한 시간초과된 풀이 >
for(int i=0; i<N; i++){
vector<int>::iterator x = --vec.end();
int num = N-i;
for(auto iter = vec.rbegin(); iter != vec.rend(); ++iter){
if(*x < *iter){
ans.push_back(num);
vec.pop_back();
break;
}
num--;
}
if(num == 0){
ans.push_back(num);
}
}1-5. 출력 📣
첫째 줄에 주어진 탑들의 순서대로 각각의 탑들에서 발사한 레이저 신호를 수신한 탑들의 번호를 하나의 빈칸을 사이에 두고 출력한다. 만약 레이저 신호를 수신하는 탑이 존재하지 않으면 0을 출력한다.
2. stack을 사용한 문제 풀이 조건 🖌️
조건
1. 자신보다 왼쪽에 있는 탑이고, 자신의 높이보다 높이가 높아야 한다.
2. 자신과 거리가 가장 짧은 탑이어야 한다.
3. 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다.
2-1. 조건 1 : 자신보다 왼쪽에 있는 탑이고, 자신의 높이보다 높이가 높아야 한다.
- 조건 1은 자신보다 먼저 선언된 탑의 높이를 가진 탑 중에서 자신이 구하고자 하는 답이 있다는 것이다. 따라서 탑의 높이를 입력받을 때마다, 전에 입력받은 탑의 높이와 비교하여 자신보다 높은 탑이 있는지를 살펴본다.
2-2. 조건 2 : 자신과 거리가 가장 짧은 탑이어야 한다.
- 즉, 탑의 높이를 입력받을 때마다 stack에 넣고, stack의 top이 자신과 가장 거리가 짧으므로 stack의 top부터 살펴본다.
2-3. 조건 3 : 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다.
- 위의 그림에서는 1번 탑과 2번의 탑은 3번의 탑보다 높이가 낮기 때문에 4,5,6번 탑에서 쏜 레이저는 모두 3번의 탑에서 받는다. 따라서 1번과 2번 탑은 stack에 있을 필요가 없다.
- 즉, stack에 있는 탑의 높이보다 넣으려는 탑의 높이가 더 높다면 이전에 있던 stack에 들어있는 탑의 높이는 pop해준다.
3. 문제 풀이 📒
- 탑의 높이를 입력 받는다.
- 이때 만약 stack이 empty인 경우, 0을 출력하고 입력 받은 값을 stack에 넣는다.
- 만약 stack이 empty가 아닌 경우, stack의 top의 높이와 입력 받은 탑의 높이를 비교한다.
- '입력 받은 높이 > top의 높이'이면, stack의 top을 pop한다.
- '입력 받은 높이 < top의 높이'이면, 해당 top의 탑 번호를 출력하고 입력 받은 탑의 높이와 번호를 stack에 넣는다.
3번의 과정을 stack이 empty이거나, 입력 받은 높이보다 높은 탑이 나올 때까지 반복한다.
예시 : 높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 수평 직선에 일렬로 서 있는 경우
1) 높이가 6인 1번의 탑을 입력받는다.
- stack이 empty이므로 0을 출력하고, 입력받은 값인 6과 탑의 번호 1을 stack에 넣는다.
2) 높이가 9인 2번의 탑을 입력받는다.
- stack이 empty가 아니므로, 입력받은 값인 9와 stack의 top의 높이 6을 비교하면 입력받은 값이 더 크므로 top을 pop한다.
- 그리고 stack이 empty이므로 0을 출력하고, 입력받은 값인 9와 탑의 번호 2를 stack에 넣는다.
3) 높이가 5인 3번의 탑을 입력받는다.
- stack이 empty가 아니므로 입력받은 값인 5와 stack의 top의 높이 9을 비교하면, stack top의 높이가 더 크므로 stack의 top의 번호 2를 출력하고 입력 받은 값인 5와 탑의 번호 3을 stack에 넣는다.
4) 높이가 7인 4번의 탑을 입력받는다.
- stack이 empty가 아니므로 입력받은 값인 7과 stack의 top의 높이 5을 비교하면, 입력받은 값이 더 크므로 top을 pop한다.
- 그리고 stack이 empty가 아니므로 입력받은 값인 7과 stack의 top의 높이 9를 비교하면, top의 높이가 더 크므로 stack의 top 번호 2를 출력하고, 입력받은 값인 7과 탑의 번호인 4를 stack에 넣는다.
5) 높이가 4인 5번의 탑을 입력받는다.
- stack이 empty가 아니므로 입력받은 값인 4과 stack의 top의 높이 7를 비교하면, top의 높이가 더 크므로 stack의 top 번호 4를 출력하고, 입력받은 값인 4와 탑의 번호인 5를 stack에 넣는다.
4. 풀이 코드 🧩
#include <iostream>
#include <stack>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int N=0; //테스트 케이스의 수
int high = 0; //탑의 높이
stack<pair<int,int>> sta1; //탑의 번호, 탑의 높이
cin>>N;
for(int n=1; n<=N; n++){
cin>>high;
while(true){
if(sta1.empty()){
cout<<0<<" ";
sta1.push({n, high});
break;
}
else{
if(high > sta1.top().second) sta1.pop(); // '입력 받은 높이 > top의 높이'이면, stack의 top을 pop한다.
else {
cout<<sta1.top().first<<" "; // '입력 받은 높이 < top의 높이'이면, 해당 top의 탑 번호를 출력하고
sta1.push({n, high}); //입력 받은 탑의 높이와 번호를 stack에 넣는다.
break;
}
}
}
}
}5. 결과 🏆
