[백준] 17298 오큰수 C++

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

해설

문제 그대로 오른쪽에서 있으면서 자신보다 큰 수를 찾아서 출력하면되는 문제이다.

스택을 사용해야한다. 현재 스택이 비어있다면 그대로 넣고 그게 아닌 경우 현재 스택의 top보다 작다면 그대로 스택에 넣고 그렇지 않다면 스택에서 빼는 작업을 해야한다.

오른쪽에 있는 수만 비교하면 되기 때문이다. 

말로는 어려우니 코드를 보면서 이해를 하도록 하자.

 

코드

#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
#include <stack>
#include <sstream>
#include <set>
#include <unordered_set>
#include <cmath>

using namespace std;
using ll = long long;
#define endl "\n"

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	int n; cin >> n;
	stack<pair<int, int>> stk;
	vector<int> ret;
	ret.resize(n);
	for (int i = 0; i < n; ++i)
	{
		int a; cin >> a;
		if (stk.empty()) stk.push({ a, i });
		else
		{
			if (stk.top().first > a)
			{
				stk.push({ a, i });
			}
			else
			{
				while (stk.empty() == false && stk.top().first < a)
				{
					ret[stk.top().second] = a;
					stk.pop();
				}
				stk.push({ a, i });
			}
		}
	}
	
	while (!stk.empty())
	{
		ret[stk.top().second] = -1;
		stk.pop();
	}

	for (int a : ret) cout << a << " ";

	return 0;
}

 

후기

왜 스택을 써야하는지 이해만 한다면 풀 수 있는 문제라고 생각한다.

핵심은 스택의 타입이 pair<int, int>로 ret에 바로 인덱스 접근을 할 수 있게 한점과 스택에 남아 있는 것들은 오큰수가 없다는 것을 명확하게 구분한 점이라고 생각한다.