17298번: 오큰수

17298번: 오큰수(BOJ C/C++)

사용 언어: C

문제

크기가 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이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.

출력

총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다.

 

풀이

먼저 코드부터!

#include <stdio.h>
#include <stdlib.h>
#define MAX 1000001

typedef struct Stack{
    int stack_arr[MAX];
    int size;
}Stack;

int empty(Stack *s)
{
    return s->size==0;
}

int top(Stack *s)
{
    return s->stack_arr[s->size-1];
}

void push(Stack *s, int num)
{
    s->stack_arr[s->size++]=num;
}

int pop(Stack *s)
{
    return s->stack_arr[--s->size];
}

int main(void)
{
    Stack* stack = (Stack *)malloc(sizeof(Stack));
    int N;
    scanf("%d",&N);
    int arr[N];
    int ans[N];
    for(int i=0;i<N;i++)
    {
        scanf("%d", &arr[i]);
        ans[i]=-1;
    }

    for(int i=0;i<N;i++)
    {
        while(!empty(stack) && arr[top(stack)] < arr[i])
            ans[pop(stack)] = arr[i];

        push(stack, i);
    }

    for(int i=0;i<N;i++)
        printf("%d ", ans[i]);

    return 0;
}

스택을 활용해야 한다. 가장 핵심 부분은 아래의 코드다.

for(int i=0;i<N;i++)
    {
        while(!empty(stack) && arr[top(stack)] < arr[i])
            ans[pop(stack)] = arr[i];

        push(stack, i);
    }

push(stack, i)로 스택에 저장하는 것은 i의 값이다. 그래서 while 문이 성립할 동안 ans[] 에서 pop을 진행하면 경우에 따라 ans[0]부터 ans[3]까지 순차적으로 arr[i]의 값이 들어가거나 이미 초기화된 -1 그대로 유지된다. while문은 스택이 비어있지 않고 스택의 맨 위의 값이 arr[i]보다 작으면 부딪혀서 조건을 만족하므로 ans[] 배열에 부딪힌 값이 저장된다. 결국 핵심은 스택에 i의 값을 저장하면서 ans에 답을 바로 저장하는 것이 아닌 i와 스택에 저장된 i의 값을 활용한 ans[pop(stack)] = arr[i] 문장이다. 설명을 잘 못했지만 알아들었길 바란다...

 

위 코드에서는 stack_arr[MAX]로 코드를 작성했지만 이렇게도 표현할 수 있다. 알아두면 다음에 더 편하게 코드를 쓸 수 있을 것 같다!

typedef struct
{
    int *stack;
    int size;
}Stack;

~~ //생략

int main(void)
{
scanf("%d", &N);
    int arr[N];
    int ans[N];
    stk->stack = calloc(N, sizeof(int)); //calloc 활용하기
 //~~
 }