[백준 17298] 오큰수

문제

백준 17298

유형

• 스택

풀이

처음에는 이분탐색으로 풀어보려고 했지만 구현하는데서 막히는 부분이 있어서 포기하고 유형을 보았다. 스택을 이용한 풀이였고 쉽게 해결할 수 있었다.

일단 pair<int, int>을 자료형으로 가지는 스택을 선언하고 pair는 값과 인덱스로 이루어져있다. 그리고 처음부터 순회하며 스택을 채워나간다.

스택을 채우는 규칙은 비어있으면 일단 푸시하고 현재 값이 스택의 top보다 크면 계속해서 스택을 비운다. 스택에 꺼낼때 해당 원소가 가지고 있는 인덱스에 현재 값을 넣는다.

말로는 어렵지만 코드를 보면 쉽게 이해할 수 있을 것이다.

코드

#include <bits/stdc++.h>

const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,-1,0,1 };

using namespace std;
int n;
int arr[1000001];


int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
	cin >> n;
	memset(arr, -1, sizeof(arr));
	stack<pair<int ,int>> s;
	for (int i = 0; i < n; i++) {
		int x; cin >> x;

		if (s.empty()) s.push({ x, i });
		else {
			while (!s.empty()) {
				if (s.top().first < x) {
					arr[s.top().second] = x;
					s.pop();
				}
				else break;
			}
			s.push({ x, i });
		}
	}

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


	return 0;
}