[백준 2493] 탑 - C++ / 알고리즘 '스택'

문제

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

2493번: 탑

나의 코드 - 하지만 시간초과....

#include <iostream>
#include <stack>

using namespace std;

int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);

	stack<int> s, result;
	stack<int> temp;
	int num, n, count;
	cin >> num;

	for (int i = 0; i < num; i++) {
		cin >> n;
		s.push(n);
	}

	while (!s.empty()) {
		int top_h = s.top();
		s.pop();
		
		//수신한 탑 찾기
		while (!s.empty()) {
			if (top_h < s.top()) {
				result.push(int(s.size()));
				break;
			}
			temp.push(s.top());
			s.pop();
		}
		if (s.empty())
			result.push(0);

		//temp -> s로 돌려보내기
		while (!temp.empty()) {
			s.push(temp.top());
			temp.pop();
		}
	}

	while (!result.empty()) {
		cout << result.top() << " ";
		result.pop();
	}
}

첫 코드는 스택s를 통해 가까운 수신탑을 찾는다.

대신 원래 스택으로 되돌아가기 위해 이전 pop 내용이 필요하므로 s에서 pop할 때마다 temp라는 스택에 쌓았다

그리고 수신탑 발견이 끝나면 temp 내용을 pop하면서 s에 push했다.

하지만 이는 너무 오래 걸렸다!!!

 

다른 사람의 코드를 살짝 살펴보다가...

스택 한가지만으로 된다는 사실을 알게 되었다.

그래서 생각한 결과 한번 수신탑이 나오면 그 이전에 숫자들은 필요가 없어진다는 것이다

pop해서 버려진 것은 어차피 현재 height보다 낮아서 수신탑이 되지 못한다. 수신탑의 가능성 있는 애들이 스택에 남아있게 된다. -> 이래서 '스택'를 쓰는 것!

 

예를들어) 

6 입력 - 스택(6,)

9 입력 - 스택(9,)   -> 6은 필요없게 된다!!

5 입력 - 스택(9, 5)

7 입력 - 스택(9, 5, 7)

4 입력 - 스택(7, 4)  -> 9, 5는 필요없게 된다!!

 

하지만 여기까지 감이 와도 대체 스택하나로 어떻게 구현하는지 감이 오지 않았다.

 

그 이유는 문제 원리를 어떻게 풀어야할지 감만 잡았지 명확한 해답이 안 나왔기 때문!

 

그래서 다시 생각해본 결과

6 입력 - 스택(6)

9 입력 - 스택(9) -> 6 pop

5 입력 - 스택(9, 5)

7 입력 - 스택(9, 7) -> 수신탑을 찾을때까지 pop하기!!!

4 입력 - 스택(9, 7, 4)

 

 

수정된 나의 소스코드

#include <iostream>
#include <stack>

using namespace std;

int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);

	stack<pair<int, int> > s;  // pair<int, int> : index, height
	int num, height;
	cin >> num;

	for (int i = 0; i < num; i++) {
		cin >> height;

		while (!s.empty()) {
			//수신탑 발견했을 때
			if (height < s.top().second) { // s.top().second
				cout << s.top().first << " ";
				break;
			}
			//수신탑 찾을 때까지 계속 pop
			s.pop();
		}
		//수신 탑이 없다면
		if (s.empty()) {
			cout << 0 << " ";
		}
		//현재 높이를 스택에 푸쉬
		s.push(make_pair(i + 1, height));
	}
	
	return 0;
}  

 

원리가 이해가 잘 안되었다면 잘 설명해준 사이트가 있다 - https://hsp1116.tistory.com/30

(나랑 소스코드 비슷해서 소오름 - 난 성장중이야 ㅠㅠㅠ)

백준 - 2493 탑

배운점

1. stack<pair<int, int> > s;

pair<type, type>를 통해 묶어서 저장이 가능하다!

((주의 사항)) error: ‘>>’ should be ‘> >’ within a nested template argument list

이러한 에러가 안나오도록 띄어쓰기를 반드시 하자!!

 

2. height < s.top().second

pair<type, type>를 썼을 때 인자로 접근하는 방법

 

https://blockdmask.tistory.com/64

[C++] Pair 클래스 정리 및 예제 (vector, sort)