Maximum Element

문제(요약)

다음 지시 따라 stack 에 데이터를 입/출력 해라

1 x  -Push the element x into the stack.
2    -Delete the element present at the top of the stack.
3    -Print the maximum element in the stack.

풀이

문제에서 출력을 요구하는 것은 최대값을 출력하기를 원하기 때문에 stack 에는 입력받은 값이 아닌 최대값을 저장하여 O(1) 에 문제를 해결할 수 있습니다.

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

int s[100000];

int main() {

    /* Enter your code here. Read input from STDIN. Print output to STDOUT */    
    int n, cmd, x;
    int sp = 0;

    scanf("%d", &n);
    for (int i=0;i<n;i++) {
        scanf("%d", &cmd);

        if (cmd == 1) {
            scanf ("%d", &x);

            if (sp == 0)
                s[sp] = x;
            else {
                if (s[sp-1] > x)
                    s[sp] = s[sp-1];
                else
                    s[sp] = x;
            }

            // printf ("[%d] @ (=%d)\n", s[sp], sp);
            sp++;
        } else if (cmd == 2) {
            s[sp--] = 0;
        } else if (cmd == 3) {

            // for (int i=0;i<sp;i++) {
            //     printf ("[%d] @ (=%d)\n", s[i], i);
            // }
            // printf("\n");
            printf ("%d\n", s[sp-1]);
        }

    }
    return 0;
}

출처

• HackerRank - Maximum Element