백준17298🐨오큰수.py .c + 백준17299🐨오등큰수.py

 

https://redcubes.tistory.com/124

🐨BOJ#6549 히스토그램에서 가장 큰 직사각형] 모노톤 스택(#1725히스토그램)

 

오큰수 (NGE: Next Greater Element)

오큰수: 현재 숫자 오른쪽에 위치하면서 현재 숫자보다 큰 수 중 가장 왼쪽에 있는 수.

예시: 숫자 배열이 [9, 5, 4, 8]일 때 각 숫자의 오큰수는 다음과 같다:

• 9: 오른쪽에 더 큰 수가 없으므로 -1
• 5: 오른쪽에 있는 8이 오큰수
• 4: 오른쪽에 있는 8이 오큰수
• 8: 오른쪽에 더 큰 수가 없으므로 -1

결과: [-1, 8, 8, -1]

모노톤 스택을 사용한 해결 방법:(이거 모노톤 스택 맞..지?)

1. 스택과 결과 리스트 초기화
   • 스택을 사용하여 오큰수를 찾는다.
   • 결과 리스트(result)는 기본적으로 -1로 초기화한다. (오큰수가 없을 경우를 대비)
2. 배열을 순회하며 처리
   • 배열의 각 요소를 순회하면서 다음을 수행한다:
     1. 현재 스택이 비어 있지 않고, 스택의 top에 있는 인덱스가 가리키는 숫자보다 현재 숫자가 큰 경우:
        • 스택의 top에 있는 인덱스를 pop하고, 해당 인덱스의 결과를 현재 숫자로 갱신한다.
        • 이 과정을 스택이 비어있거나 스택의 top에 있는 숫자가 현재 숫자보다 클 때까지 반복한다.
     2. 현재 숫자의 인덱스를 스택에 push한다.
3. 결과 반환
   • 배열을 모두 순회한 후 결과 리스트를 반환한다.

코드 (Python):

def nge(n, arr):
    result = ["-1"] * n
    stack = []

    for i in range(n):
        while stack and arr[stack[-1]] < arr[i]:
            index = stack.pop()
            result[index] = str(arr[i])
        stack.append(i)
    return result
n, *arr = map(int,open(0).read().split())
open(1,'w').write(' '.join(nge(n, arr)) + '\n')

얼라리요?

단계별 설명:

1. 스택과 결과 리스트 초기화
   • result 리스트는 모든 값을 "-1"로 초기화하여, 오큰수가 없는 경우 기본값으로 사용된다.
   • stack은 인덱스를 저장하여 모노톤 스택을 구현한다.
2. 배열 순회
   • 배열의 각 요소를 순회하면서, 현재 숫자가 스택의 top에 있는 숫자보다 큰 경우 해당 인덱스의 값을 현재 숫자로 업데이트한다.
   • 현재 숫자의 인덱스를 스택에 추가하여 다음 비교를 위해 준비한다.
3. 결과 반환
   • 모든 요소를 순회한 후 완성된 result 리스트를 반환하여 최종 오큰수를 확인한다.
4. 포인트
   스텍에 인덱스를 저장해서 원래의 배열에서 숫자를 가져와서 비교함.
   이렇게 안 하면 스택에 튜플 저장해야 함.

 

동적 메모리 할당을 통한 C언어 코드

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

int main() {
    int n;
    scanf("%d", &n);

    int *arr = (int *)malloc(n * sizeof(int));
    int *stack = (int *)malloc(n * sizeof(int));
    int *result = (int *)malloc(n * sizeof(int));
    int top = -1; // 스택의 최상단 인덱스

    // 배열 값 읽기
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
        result[i] = -1; // 초기값 설정
    }

    // 다음 큰 요소 찾기
    for (int i = 0; i < n; i++) {
        while (top != -1 && arr[stack[top]] < arr[i]) {
            result[stack[top]] = arr[i];
            top--;
        }
        stack[++top] = i;
    }

    // 결과 출력
    for (int i = 0; i < n; i++) {
        if (i != 0) printf(" ");
        printf("%d", result[i]);
    }
    printf("\n");

    // 메모리 해제
    free(arr);
    free(stack);
    free(result);

    return 0;
}

 

리스트에 포인터를 저장하는 방식의 C코드

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

int main() {
    int n;
    scanf("%d", &n);

    int *arr = (int*) malloc(n * sizeof(int));
    int *result = (int*) malloc(n * sizeof(int));
    int **stack = (int**) malloc(n * sizeof(int*));
    int top = -1;

    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    for (int i = 0; i < n; i++) {
        while (top != -1 && *stack[top] < arr[i]) {
            int *index = stack[top--];
            result[index - arr] = arr[i];
        }
        stack[++top] = &arr[i];
    }

    while (top != -1) {
        int *index = stack[top--];
        result[index - arr] = -1;
    }

    for (int i = 0; i < n; i++) {
        printf("%d ", result[i]);
    }
    printf("\n");

    free(arr);
    free(result);
    free(stack);

    return 0;
}

위 문제에 빈도를 한 번 세고 빈도를 비교하면 되는 문제다.

from collections import Counter


def ngf(n, arr, f):
    result = ["-1"] * n
    stack = []

    for i in range(n):
        while stack and f[arr[stack[-1]]] < f[arr[i]]:
            index = stack.pop()
            result[index] = str(arr[i])
        stack.append(i)
    return result
n, *arr = map(int,open(0).read().split())
f = Counter(arr)
open(1,'w').write(' '.join(ngf(n, arr, f)) + '\n')