[백준 2493/C++] 탑

1. 문제

https://www.acmicpc.net/problem/2493

2493번: 탑

---

2. 문제 풀이

#include <iostream>
#include <bits/stdc++.h>
#pragma warning (disable:4996)

using namespace std;

stack<pair<int,int>> s;
int n, x; 

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	s.push({ 100000005,0 });
	for (int i = 1; i <= n; i++) {
		int x; 
		cin >> x;
		while (s.top().first <= x)
			s.pop();
		cout << s.top().second << ' ';
		s.push({ x, i });
	}
}

---

3. 문제 평가 및 해설

 

일단, 이 문제는 이중 for문으로 O(N^2)으로 해결하면 당연히도 시간초과가 나는 문제이다.

 

처음, 문제를 보고 스택 자료구조로 풀어야겠다는 생각이 전혀 안잡혔다.

 

바킹독님의 강의를 통해 해당 문제를 접할 수 있었는데, 스택이라는 단원의 문제임에도 불구하고 "이걸 어떻게 스택으로 해결하지?"라는 생각이 계속들었다.

 

오래 생각해도 풀이가 도저히 생각나지 않아서, 풀이를 참조했다.

 

문제 풀이는 다음과 같다.

1. 먼저 pair 자료형을 사용해서, 높이와 순서를 모두 받는 스택을 만든다. 

=> 이 부분이 내가 생각하지 못한 방법이다. 스택은 높이를 받고, 순서는 배열을 통해 해결하려했다. 

2. 스택의 최하단에 {100000005의 높이, 0}를 가진 탑을 넣어준다.

=> 이 문제의 핵심이다. 이 방법을 사용하지 않고 스택에서 해결하려하면, 스택이 빈 상태에서 s.top(), s.pop()을 참조하려하면 런타임에러가 난다. 하지만 이 방법으로 코드를 짜면, 런타임 에러의 지옥에서 벗어나게 해준다

3. push를 하기 전, 비교를 해준다. push를 하려고 하는 수가 스택의 top보다 크다면, 수신을 못한다는 것이니 pop을 해준다.

4. top을 출력하고, push를 해준다.

 

내 풀이는 바킹독님의 풀이를 참조했다 :)

https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x05/solutions/2493.cpp