[BaekJoon]백준 2493번 탑
문제: https://www.acmicpc.net/problem/2493
내코드
- 처음엔 정석대로 모든 입력값을 stack에 넣어서 top부터 차례대로 밑에것들이랑 비교하려고함. 그렇게 하면 더 복잡하단걸 깨달음.
- stack과 pair를 이용함. stack에는 차례대로 입력을 받고, pair에는 입력값과 index값을 순서대로 저장함.
- n개의 탑이 있을때 가장 왼쪽에 있는 것부터 차례대로 입력을 받음(ex. 69574)
- 우선 첫번째 6이 들어왔을때 stack이 비어있는지 확인하고 비어있으니 0 출력, 출력후 (1, 6) pair로 stack에 쌓음.
- 두번째 9가 들어왔을때 stack이 비어있는지 확인하고 안비어있으니 while문으로 들어가서 top의 값과 비교. top의 값과 비교했을때 top이 더 작으므로 레이저가 의미가 없으므로 top을 pop시킴(어차피 현재 input 값, 즉 9가 더 크니까 이후 들어오는 input값은 9에서 막힘. 따라서 6이란 값은 더이상 필요없음), 다시 while문 처음으로 돌아갔을때 stack은 비어있으므로 0 출력 후 해당 input 값 pair로 stack에 쌓음.
- 반복
- 결론: 매 input 값마다 stack의 top과 비교해주며 top이 더 작으면 pop 후 다음 top 값과 비교해준다. top이 더 크면 해당 top 값을 출력(레이저에 부딪히므로). 만약 stack이 비어있으면 레이저가 아무 탑이랑도 부딪히지 않았다는 의미이므로 0을 출력해줌.
- 너무 복잡하게 생각하지 않기. 미리 생각해보고 코드짜기 시작하기. stl 활용하기. 문제에서 원하는 포인트 뭔지 생각.
- 포인트: 해당 탑보다 오른쪽 탑에 더 큰 수가 나왔을때 해당 탑은 더이상 그 이후의 탑에 영향을 끼치지 않으므로 pop해줘도 상관없음.
#include <iostream>
#include <string>
#include <stack>
#include <utility>
using namespace std;
int tmp, n;
stack<pair<int, int>> stk;
int main(void)
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
//number of top
for (int i = 0; i < n; i++) {
cin >> tmp;
//if stack is not empty check the top with input
while (!stk.empty()) {
if (stk.top().second > tmp) {
//if top is bigger than input print index of top
//+1 bcz stack starts from 0
cout << stk.top().first + 1 << " ";
break;
}
//if top is not bigger than input pop the top
stk.pop();
//and then check the next one (under the top)
//if there's no more element that is bigger than input stack'll be empty
}
//if stack is empty print 0
if (stk.empty()) cout << 0 << " ";
//push the current top
stk.push(make_pair(i, tmp));
}
return 0;
}
참고
https://hsp1116.tistory.com/30
https://blockdmask.tistory.com/64 (STL pair)
'CS > Algorithm 문제' 카테고리의 다른 글
[BaekJoon] 백준 2178번 미로탐색 (0) | 2020.02.25 |
---|---|
[BaekJoon] 백준 1926번 그림 (0) | 2020.02.21 |
[Baekjoon]백준 2504번 괄호의 값 (0) | 2020.01.23 |
[BaekJoon] 백준 10799번 쇠막대기 (0) | 2019.12.12 |
[BaekJoon]백준 9012번 괄호 (0) | 2019.12.03 |