https://www.acmicpc.net/problem/2493
문제분석
맨 오른쪽부터 왼쪽으로 일정 높이를 가진 탑에서 신호를 송신하면 신호를 보낸 탑보다 높이가 높은 탑만 신호를 수신할 수 있다.
예를 들어 높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 수평 직선에 일렬로 서있다고 하자. 그러면, 높이가 4인 다섯번째 탑에서 발사한 레이저 신호는 높이가 7인 네 번째 탑이 수신을 하고, 높이가 7인 네 번째 탑의 신호는 높이가 5인 탑을 지나쳐 높이가 9인 탑이 수신을 한다.
높이가 9인 두 번째 탑과 높이가 6인 첫 번째 탑이 보낸 레이저 신호는 어떤 탑에서도 수신하지 못한다.
입력으로는 첫째 줄에는 탑의 개수 N이 주어지고, 두번째 줄에는 각각 탑들의 높이가 주어진다.
출력으로는 각각의 탑에서 바라한 레이저 신호를 어느 탑에서 수신하는지를 출력한다.
코드
#include <iostream>
#include <stack>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
stack<pair<int,int>> s; // 인덱스와 탑의 높이를 같이 저장할 pair쌍
int n, num;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> num;
while (!s.empty()) { // 스택이 비어있지 않으면
if (num < s.top().second) { // 스택 최상단에 저장된 탑의 높이와 비교
cout << s.top().first << " "; // 수신가능하면 스택 최상단에 있는
// 탑의 인덱스를 출력
break;
}
s.pop(); // 높이가 낮으면 어차피 쓸모없으므로 Pop
}
if (s.empty()) { // 만약 스택이 비어있다면 = 수신할 수 있는 것이 없다 = 0 출력
cout << 0 << " ";
}
s.push({ i + 1, num }); // 현재 탑을 스택에 push
}
return 0;
}
문제풀이
우선 값을 입력받고, 스택을 체크한다. 스택을 체크하였는데 비어있다면 내 왼쪽에는 탑이 없는 것이므로 0을 출력해준다.
만약 스택에 값이 들어있다면, 현재 입력으로 들어온 것과 스택의 top()과 비교를 한다.
만약 현재 입력값 > 스택의 top()이라면, 수신할 수 없는 탑이므로 pop하여 다음 스택값과 비교한다.
이를 스택이 빌 때 까지 반복한다.
반복하는 도중에
만약 현재 입력값 < 스택의 top()이라면, 정상적인 탑을 찾은 것이므로 스택의 top()에 해당하는 탑의 인덱스를 출력한다.
그리고 현재 입력으로 들어온 값과 인덱스를 pair쌍으로 스택에 저장한다.
※ 이 문제를 쉽게 해결하기 위해선 pair를 떠올리는 것이 중요했던 것 같다.
원문
https://blog.naver.com/oh2279/222642836934
'Koala - 5기 > 기초 알고리즘 스터디' 카테고리의 다른 글
[BOJ/python] 10989번 수 정렬하기 3 (0) | 2022.02.13 |
---|---|
[백준 / python] 2566번 최댓값 (0) | 2022.02.12 |
[백준/C++] 14593번 2017 아주대학교 프로그래밍 경시대회 (Large) (1) | 2022.02.07 |
[백준/python] - 13410번: 거꾸로 구구단 (0) | 2022.02.07 |
[백준/python] 10773번 제로 (0) | 2022.02.07 |