백준 17298 C++

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

17298번: 오큰수

이 문제는 아이디어만 생각하면 굉장히 쉬운 문제가 된다.

 

처음에는 작은게 왼쪽, 큰게 오른쪽으로가는 이진 트리를 생각했다가

같은 값이 들어왔을 경우의 반례가 생겨서 계속 고민을 했다.

 

결국엔 Stack으로 풀면 된다.

비슷한 문제로는 균형잡힌 세상, 괄호가 있다.

 

처음부터 생각을 하진 못했다. 지금까지 Stack을 활용한 짝짓기 문제는 1:1로 대응됐기 때문이다.

하지만 이 문제부터 짝짓기는 1:1로 정의되는 것이 아니라

n:1로 로 생각했다.

 

위 문제들은 1:1 대응이고현재 문제는 이전에 들어왔던 값(a)이 이후에 들어오는 값(b)보다 작으면a의 결과는 b로 출력을 해야하고다시 stack에 있는 값과 b를 비교해서 출력값을 정해야한다.그러므로 n:1이 된다.

#include <iostream>
#include <stack>
#include <cstring>

using namespace std;

int n;
stack<pair<int, int>> s;
int result[1000001];

int main() {
	cin >> n;
	memset(result, -1, sizeof(result));

	for (int i = 0; i < n; i++) {
		int a; cin >> a;
		if (s.empty() || s.top().first >= a) {		//스택이 비어있거나 top의 숫자가 현재 들어온 수보다 클 경우
			s.push(make_pair(a, i));
		}
		else {
			while (1) {
				if (s.empty() || s.top().first >= a) break;
				result[s.top().second] = a;		//result[자신 순번]에 오큰수 입력
				s.pop();
			}
			s.push(make_pair(a, i));		//자기 자신도 Stack에 넣어야하기 때문에 다 빼고나서 넣는다.
		}
	}

	for (int i = 0; i < n; i++) {
		cout << result[i] << " ";
	}
}