백준 오큰수(17298번) C언어

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

17298번: 오큰수

---

문제

크기가 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)을 공백으로 구분해 출력한다.

---

해결방안 -> 백준 2493과 비슷하면서 살짝 다른 문제이다. 탑에서는 왼쪽부터 스택을 활용한다면 이번에는 수열을 모두 입력받고 오른쪽부터 진행해나간다. 

수열 Ai에 대한 오큰수를 저장하는 배열 IDX를 선언해준다.

오른쪽부터 왼쪽으로 진행해가면서 스택이 비어있다면 Push연산 후 IDX[Ai]에 -1을 저장한다.

만약 스택의 Top값이 수열 Ai값보다 크다면 IDX[Ai]값에 스택의 Top값을 넣어주고 Push연산을 한다.

먄약 스택의 Top값이 수열 Ai보다 작거나 같다면 

 

Pop연산 후 -> 스택이 비어있음 or Top값이 수열의 값보다 큰 경우로 나눈다.

 

Pop연산 후 스택이 비어있다면 Push연산 후 IDX[Ai]값을 -1로 지정한다 ->그 후 break문

Pop연산 후 Top값이 수열의 값보다 크다면 IDX[Ai]값을 Top값으로 지정하고 Push연산을 한다->마찬가지로 break문

---

오른쪽부터!

---

!

---

전체 소스 코드->

#include <stdio.h>

#define LEN 1000000

#define True 1

#define False 0

 

typedef struct _cstack{

    int arr[LEN];

    int topindex;

}CSTACK;

 

typedef CSTACK Stack;

 

void Stackinit(Stack *pstack){

    pstack->topindex = -1;

}

 

int Empty(Stack *pstack){

    if(pstack->topindex == -1){

        return True;

    }

    else{

        return False;

    }

}

 

void Push(Stack *pstack,int data){

    pstack->topindex = pstack->topindex + 1;

    pstack->arr[pstack->topindex] = data;

}

 

void Pop(Stack *pstack){

    pstack->topindex = pstack->topindex - 1;

}

 

int Top(Stack *pstack){

    return pstack->arr[pstack->topindex];

}

 

int main(void){

    Stack stack;

    Stackinit(&stack);

    int array[LEN];

    int IDX[LEN];

 

    int n;

    scanf("%d",&n);

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

        scanf("%d",&array[i]);

    }

 

    for(int i = n-1;i>=0;i--){

        if(Empty(&stack)){

            Push(&stack,array[i]);

            IDX[i] = -1;

        }

        else{

            if(Top(&stack) > array[i]){

                IDX[i] = Top(&stack);

                Push(&stack,array[i]);

 

            }

            else if(Top(&stack) <= array[i]){

                while(!Empty(&stack)){

                    Pop(&stack);

                    if(Empty(&stack)){

                        Push(&stack,array[i]);

                        IDX[i] = -1;

                        break;

                    }

                    else if(Top(&stack) > array[i]){

                        IDX[i] = Top(&stack);

                        Push(&stack,array[i]);

                        break;

                    }

                }

            }

        }

    }

 

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

        printf("%d ",IDX[i]);

    }

}