[알고리즘/문제풀이/BOJ 17298번] 오큰수

오큰수 문제는 스택을 활용하여 풀 수 있는 문제이다. 입력의 수가 1000,000이기 때문에 O(N^2)의 알고리즘으로는 풀 수가 없다. 스택을 활용하면 O(N)으로 풀 수 있게 된다. 아이디어는 다음과 같다.

수열을 순차적으로 탐색하면 어떤 수의 다음 수로 작거나 같은 수가 올 수 있고 혹은 큰 수가 올 수 있다.
작은 수가 오게 된다면 그것은 어떤 수의 오큰수가 되지 못하기 때문에 어떤 수의 오큰수를 바로 결정하지 못하고 다음에 결정할 수 있도록 어떤 수를 저장해야 한다.
큰 수가 온다면 그것은 오큰수가 될 수 있기에 어떤 수의 오큰수를 결정한 후 이전에 저장한 오큰수를 결정하지 못한 다른 수들에 대해 판단을 하여야 한다.
가만히 살펴보면 저장되는 수는 내림차순으로 저장되며 오큰수를 판별할 때는 오름차순으로 판단하는 것이 타당하다고 생각된다.
이러한 내림차순 저장과 오름차순 판별은 LIFO 구조의 자료 입출력이며 스택의 사용을 암시한다. 

주의할 점은 스택에 아무것도 없다면 반드시 스택에 저장해야 한다.

시간은 N개의 자료를 한 번씩 push, pop 하므로 O(N)이 걸린다.

작성한 코드는 다음과 같다.

---

#include<stdio.h>
//https://ark-hive.tistory.com/
int N;

int stack[1000020];
int top;

int NEG[1000020];
int element[1000020];

//수열을 순차적으로 탐색하면 어떤 수의 다음 수로 작거나 같은 수가 올 수 있고
// 혹은 큰 수가 올 수 있다.
//작은 수가 오게 된다면 그것은 오큰수가 되지 못하기 때문에 어떤 수의 오큰수를 바로 결정하지 못하고 다음에 결정할 수 있도록 어떤 수를 저장해야 한다.
//큰 수가 온다면 그것은 오큰수가 될 수 있기에 어떤 수의 오큰수를 결정한 후 이전에 저장한 오큰수가 결정되지 못한 다른 수들에 대해 판단을 하여야 한다.
//가만히 살펴보면 저장되는 수는 내림차순으로 저장되며 오큰수를 판별할 때는 오름차순으로 판단하는 것이 타당하다고 생각된다.
//이러한 내림차순 저장과 오름차순 판별은 LIFO 구조의 자료 입출력이며 스택의 사용을 암시한다. 
//N개의 자료를 한 번씩 push, pop 하므로 O(N)이 걸린다.
void push(int num) {
	top += 1;
	stack[top] = num;
}

void pop() {
	if (top == 0) return;
	else {
		top -= 1;
	}
}

int main(void) {
	scanf("%d", &N);

	for (int i = 0; i < N; i++) {
		scanf("%d", &element[i]);
		while (element[stack[top]] < element[i] && top!=0) {
			NEG[stack[top]] = element[i];
			pop();
		}
		if (element[stack[top]] >= element[i] || top==0) {
			push(i);
		}
	}

	/*while (top != 0) {
		NEG[stack[top]] = -1;
		pop();
	}*/

	for (int i = 0; i < N; i++) {
		if (NEG[i] == 0) printf("%d ", -1);
		else printf("%d ", NEG[i]);
	}
}

문제의 지문은 다음 링크에서 확인할 수 있다.

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