백준 17298 오큰수

작성일 | In |

Problem : 오큰수

유형 : 스택

문제 설명

크기가 N인 수열 A = A1, A2, …, AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.

예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.

예제 입력

1
2
4
9 5 4 8

예제 출력

1
-1 8 8 -1

해결 전략

새로운 숫자가 스택 top의 숫자 보다 크다면
따로 관리하고 있는 배열 answer에 위치 별 값을 저장하고, stack에서 제거한다.
스택에는 더 큰 수를 만나지 못한 숫자들의 집합이 유지된다.

방금 들어온 숫자는 우측에 아무런 숫자가 없으므로 항상 스택에 들어간다.

주의할 점

  • 순차적으로 순열을 진행하며 더 큰수를 찾는다.

풀이

숫자를 입력받을때, 스택의 top와 대소여부를 확인한다.

  • 새로운 숫자가 들어왔을때 스택의 top과 비교한다.
  • 만약 top이 새로운 숫자보다 작다면, top은 보다 큰 수 중에서 가장 왼쪽에 있는 수를 찾았다.
    • 이제 이후에 더 큰 숫자가 나온다고 해도 top에게는 의미가 없는 숫자이니 top을 pop한다.
  • 새로 들어온 숫자는, 아직 우측 숫자가 아예 없으므로 스택에 들어간다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>

#define pp pair<int, int>
#define MAX 1000001
#define index first
#define value second

using namespace std;

int n, answer[MAX];
stack<pp> s;

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

void solve() {
	int num;
	for (int i = 0; i < n; ++i) {
		cin >> num;
		while (!s.empty()) {
			auto cur = s.top();
			if (cur.value >= num) break;
			answer[cur.index] = num;
			s.pop();
		}
		s.push({ i,num });
	}
}

void input() {
	memset(answer, -1, sizeof(answer));
	cin >> n;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//freopen("input.txt", "r", stdin);

	input();
	solve();
	output();

	return 0;
}

피드백

범위가 10만이 아니고 100만이다..