[C++] 2493번 : 탑

기술하기에 앞서 정말 배운 것이 많은 문제입니다. (STL 中 Pair Class,출력초과,monotonic stack)

풀이

1874번 스택 수열을 풀어보셨다면 접근 자체는 할 수 있었을 것 같습니다.

직관적으로 생각나는 풀이는 O(N^2) 풀이입니다. 하지만 주어진 범위를 보면 당연히 안되는 것을 알 수 있습니다.

처음 짠 코드는 정말 idea 자체만 겹쳤습니다. 도대체 index를 어떻게 처리해줘야할 지 모든 경우의 수를 동원해도 안되더군요.

같이 저장할 순 없을까?라는 생각을 하고 깊게 생각해보진 못했습니다.

#include <bits/stdc++.h> //첫 코드
using namespace std;
int main() {
	cin.tie(0);ios::sync_with_stdio(0);
	int N, cnt = 0;
	cin >> N;
	stack<int> s;
	while (N--) {
		int num;
		cin >> num;
		if (s.empty() || s.top() < num) {
			cout << cnt << ' ';
			if (!s.empty()) {
				s.pop();
				cnt--;
			}
			s.push(num);
			cnt++;
		}
		else {
			cout << cnt << ' ';
			s.push(num);
			cnt++;
		}
	}
}

 

그래서 정답 코드를 살짝 보니 Pair 객체를 Stack에 담는 방식을 사용하더군요!

그 후 저 로직을 이용하여 구현해봤는데 출력초과가 나왔었습니다.

+)Pair class를 사용하기 위해서는 utility library를 include해주어야 합니다.

https://modoocode.com/299

C++ 레퍼런스 - utility 라이브러리

Stack의 element type이 pair 객체이기 때문에 make_pair method를 통해 push해줘야합니다.

그리고 top에 접근할 때 first와 second method를 이용하여 접근할 수 있었습니다.

출력 초과가 무엇인지 찾아보니 원하는 결과보다 더 많이 출력된 것으로 사실상 오답이었습니다.

그래서 또 재도전한 결과 정답 처리가 되었는데요.

코드

#include <bits/stdc++.h>
using namespace std;
int main() {
	cin.tie(0);ios::sync_with_stdio(0);
	int N;
	cin >> N;
	stack<pair<int,int> > s; //cnt-value
	for(int i = 0; i < N; i++){
		int num;
		cin >> num;
		while (!s.empty() && s.top().second < num) {
			s.pop();
		}
		if (s.empty()) {
				cout << 0 << ' ';
				s.push(make_pair(i + 1, num));
		}
		else {
			cout << s.top().first << ' ';
			s.push(make_pair(i + 1, num));
		}
	}
}

 

사실 O(N^2)일 줄 알고 당연히 시간초과나겠구니 하면서 제출한 건데 정답처리 되더라고요.

사실 조금만 생각해보면 pop이 매 loop마다 최악의 경우 n번을 보장하지 않음을 알 수 있어요.따라서 각 연산이(push,pop:O(1)) 선형적으로 분포하게 되므로 O(N)이 보장되는데요.이에 대한 자세한 개념은 Monotonic Stack을 검색하시면 나온답니다.https://www.geeksforgeeks.org/introduction-to-monotonic-stack-data-structure-and-algorithm-tutorials/

Introduction to Monotonic Stack - Data Structure and Algorithm Tutorials - GeeksforGeeks

+)Vector을 이용하여 stack처럼 구현하신 분도 계셨습니다. 이 경우 Pair을 사용하지 않고 2개의 Vector을 사용하였습니다.