JUST WRITE IT. HomeArchivesTagsCategories
백준 17298번 오큰수
|AlgorithmBOJ|

#17298. 오큰수

문제링크

Problem

  • 길이가 N인 수열

Goal: 각 원소에 대해 자신보다 오른쪽에 있으면서 크고 가장 왼쪽에 위치한 수를 구하여라
없다면 -1 출력

Solution

  • Stack을 사용한다.
  • 단계는 문제에 예시로 있는 입력 값으로 설명을 하겠다.

Untitled

오른쪽 순서로 단계가 진행된다.

  1. 원소의 최댓값은 최대 1000000(백만)이기에 +1값을 MAX로 주었다.
  2. 수열의 맨 오른쪽부터 진행한다.
  • 사이클
    1. 비교 대상인 입력값과 스텍에 있는 값을 비교하여 스텍에 있는 값이 클 때까지 작업(비교)을 수행한다.
    2. 만약 MAX가 스텍의 top이라면 이미 자신보다 큰 수가 없다는 뜻이기에 -1를 출력값에 넣어준다.
    3. 그게 아니라면 스텍의 top은 항상 현재 입력값보다 크면서 가장 오른쪽에 있는 수이다. 그렇기에 top을 출력값에 넣어준다.

1 Try

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
#include <cstdio>
#include <stack>
#include <vector>
#define MAX 1000001
using namespace std;
stack<int> a, ans, num;
int main() {
	int n, input;
	scanf("%d", &n);
	for(int i = 0; i < n; ++i) {
		scanf("%d", &input);
		num.push(input);
	}
	a.push(MAX);
	while(!num.empty()) {
		while(a.top() <= num.top()) a.pop(); // 같을 때도 pop을 해주어야 다음 큰 값을 비교가능
		if(a.top() == MAX) ans.push(-1);
		else ans.push(a.top());
		a.push(num.top()); num.pop();
	}
	while(!ans.empty()) {
		printf("%d ", ans.top());
		ans.pop();
	}
	printf("\n");
	return 0;
}
Algorithm