[Python] 백준 : 오큰수 17298, stack, 스택

 

 

📝 문제

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

 

🫠 나의 풀이 (시간 초과)

import sys
sys.stdin = open('input.txt', 'r')
# input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
lst = [-1] * N

for i in range(N - 1):
    j = i

    while j < len(A):
        if A[j] > A[i]:
            lst[i] = A[j]
            break

        j += 1

print(*lst)

 

🧞‍♂️ 다른 사람의 풀이

import sys
sys.stdin = open('input.txt', 'r')
# input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
lst = [-1] * N
stack = [0]

for i in range(1, N):
    while stack and A[stack[-1]] < A[i]:
        lst[stack.pop()] = A[i]
    stack.append(i)

print(*lst)

 

내 풀이는 j 를 올리며 모든 인덱스를 확인하고 있지만,

아래 풀이는 각 요소에 대해 스택을 한 번씩만 탐색하고 있다.

 

 

 

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