오큰수 & 오등큰수

오큰수

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

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdbool.h>
 
struct {
    int num;
    int idx;
}typedef info;
 
int oh[1000004];
info st[1000004];
int arr[1000004];
int genzai = 0;
 
int main() {
    int n;
    scanf("%d", &n);
 
    // -1로 stack idx 초기화
    int genzai = -1;
 
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
        oh[i] = -1;
 
        // stack이 비어있지 않다면
        if (genzai != -1) {
            while (st[genzai].num < arr[i] && (genzai >= 0)) {
                oh[st[genzai].idx] = arr[i];
                // pop
                genzai--;
            }
        }
 
        // push
        genzai += 1;
        st[genzai].num = arr[i];
        st[genzai].idx = i;
    }
 
    for (int i = 0; i < n; i++)
        printf("%d ", oh[i]);
    printf("\n");
 
 
    return 0;
}

 

오등큰수

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

#include <stdio.h>
#include <stdlib.h>
int stack[1000000], cnt[1000001] = { 0 };
int idx = -1;
void push(int value) {
    stack[++idx] = value;
}
 
int pop() {
    return stack[idx--];
}
 
int is_empty() {
    return (idx == -1);
}
 
int peek() {
    return stack[idx];
}
 
int main() {
    int n;
    scanf("%d", &n);
    int* arr = (int*)malloc(sizeof(int) * n);
 
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
        cnt[arr[i]]++;
    }
 
    for (int i = 0; i < n; i++) {
        // stack이 비어있지않고 arr[i]의 cnt값이 더 크다면
        while (!is_empty() && cnt[arr[peek()]] < cnt[arr[i]]) {
            arr[pop()] = arr[i];
        }
        push(i);
    }
 
    // 스택에 남아있는 idx 값들에 -1 넣어준다
    while (!is_empty()) {
        arr[pop()] = -1;
    }
 
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
}