[C] 백준 17298번: 오큰수

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

17298번: 오큰수

 

#include <stdio.h>
#include <stdlib.h>
#pragma warning(disable:4996)

typedef struct Node {
	int var;
	int index;
	struct Node* next;
}Node;

typedef struct Stack {
	int size;
	Node* top;
}Stack;

Node* getNode(int var, int index) {
	Node* res = malloc(sizeof(Node));
	res->next = NULL;
	res->var = var;
	res->index = index;
	return res;
}

void push(Stack* stack, int var, int index) { 
	Node* newNode = getNode(var, index);
	newNode->next = stack->top;
	stack->top = newNode;
	stack->size += 1;
}

Node pop(Stack* stack) {
	Node res;
	res.index = -1;
	res.var = -1;
	res.next = NULL;
	if (stack->size <= 0) return res;

	Node* next = stack->top->next;
	res.var = stack->top->var;
	res.index = stack->top->index;

	free(stack->top);
	stack->top = next;
	stack->size -= 1;

	return res;
}

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

	int i;
	int* res = malloc(sizeof(int) * N);
	
	Stack* stack = malloc(sizeof(Stack));
	stack->size = 0;
	stack->top = NULL;

	int* nums = malloc(sizeof(int) * N);
	for (i = 0; i < N; i++) {
		res[i] = -1;
		scanf("%d", &nums[i]);
		
		while (stack->size >= 1 && stack->top->var < nums[i]) {
			Node popped = pop(stack);
			res[popped.index] = i;
		}

		push(stack, nums[i], i);
	}

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

	free(res);
	free(nums);

	return 0;
}

 

스택을 이용하여 풀 수 있는 문제이다.

 

아이디어는 다음과 같이 떠올릴 수 있었다. 9 5 4 8이 순차적으로 들어온다고 했을 때, 9 5 4가 스택에 있다고 해보자. 그 다음 8이 들어오는데, 직관적으로 생각해보면, 8보다 작은 5, 4가 사라지고 스택에는 9 8만 남아있어야 할 것 같다고 느꼈다. 그럼 스택에 있는 숫자들의 의미는 '아직 오큰수를 만나지 못한 수들'가 된다. 스택에 어떤 숫자들이 있다는 것은, 아직 그것들보다 큰 수를 못 찾은 것이고, 만약 더 큰 숫자를 만나게 되면 그것들을 없애주는 것이다.

이를 일반화하면, 수가 들어왔을 때

 - 스택의 top보다 큰 경우: 스택을 계속해서 pop해간다. 이 때 pop을 한다는 것은 스택에 저장되어 있는 숫자의 오큰수가 현재 들어온 수가 되는 것이므로 이를 res에 잘 저장해준다. 이번에 들어온 큰 수는 오큰수를 찾아나가야 하므로 push해준다.

 - 스택의 top보다 작거나 같은 경우: 아무런 처리를 하지 않고, 현재 들어온 수를 push 해준다.

가 된다.

이것은 while문으로 깔끔하게 처리할 수 있으며, 두 경우 모두 이번에 들어온 숫자를 마지막에 push해주므로(중첩) 굳이 분기문으로 나눌 필요가 없어진다.