[BaekJoon/백준] 17298 스택 활용

어려운 문제. 오큰수 문제.

 

배열로 받아서 기본적인 발상대로 앞에서부터 뒤로 구해보면 O(N^2) -> 1000000일 경우 시간초과.

따라서 이 방법은 안되고, O(N)의 방법을 찾아야 했다.

 

 

설명은 여기 블로그가 좋았다

suhwanc.tistory.com/58

백준 17298번 오큰수

 

중요한 점은 스택을 이용한다는 것과, 값 자체가 아닌 인덱스를 스택에 넣어줘서 관리한다는 것.

처음에 값을 넣어줬다가 어려움을 겪었다 ㅎㅎ..

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

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

void push(IntStack *s, int a) {
    s->stack[s->size++] = a;
}

int pop(IntStack *s) {
    return s->stack[--s->size];
}

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

int IsEmpty(IntStack *s) {
    return (s->size == 0);
}



int N;
int *arr;
int *ans;

int main() {
    IntStack stk;

    scanf("%d", &N);
    stk.stack = calloc(N, sizeof(int));
    stk.size = 0;

    arr = calloc(N, sizeof(int));
    ans = calloc(N, sizeof(int));


    for(int i = 0; i < N; i++) {
        scanf("%d", &arr[i]);
        ans[i] = -1; // 초기화 여기서 같이.
    }


    for(int i = 0; i < N; i++) {

        while(!IsEmpty(&stk) && arr[top(&stk)] < arr[i]) {
            ans[pop(&stk)] = arr[i];
        }

        push(&stk, i);

    }

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

흐름