[BOJ/C++] 17298(오큰수)

Link

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

풀이 과정

• 중복된 수가 안 나올거라고 감히 예단해서 코드를 다시 뜯어고친 케이스입니다. 처음부터 같은 수가 2회 이상 나올 가능성을 염두하면 수월할 것입니다.

• 사실 벡터 기반으로 뒤에서부터 조건에 따라 자르면서 풀려고 했는데, 생각해보니 그 방법이 스택 그 자체라서 운 좋게 시간을 단축했습니다.

1. 오른쪽에 있으면서 A_i보다 큰 수 중에 가장 왼쪽(A_i와 좌측 최근접) -> 스택

• 벡터를 활용하면 메모리 측에서 이득을 볼 것이라 생각했지만, 백만 단위의 연산에 있어서 벡터는 시간적으로 불리할 것으로 판단하여 다음과 같이 작성하였습니다.

정답 코드

#include<iostream>
#include<stack>
using namespace std;
#define MAX 1'000'000

int n;
int num[MAX], answer[MAX];

void input() {
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> num[i];
	}
}

void solution() {
	input();
	stack<int> s;
	for (int i = 0; i < n; ++i) {
		while (!s.empty()) {
			if (num[s.top()] < num[i]) {
				answer[s.top()] = num[i];
				s.pop();
			}
			else break;
		}
		s.push(i);
	}
	for (int i = 0; i < n; ++i) {
		if (answer[i] == 0) cout << -1 << ' ';
		else cout << answer[i] << ' ';
	}
}

int main() {
	cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0);
	solution();
	return 0;
}