오큰수

문제링크

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

 

가장 쉽게 생각할 수 있는...

for문 2개를 이용해서 기본이 되는 코드를 짜봤다!

from collections import deque

n = int(input())

nums = deque(map(int, input().split()))

for i in range(n):
    num = nums.popleft()
    for j in nums:
        if j > num:
            print(j, end=' ')
            break
    else:
        print(-1)

결과는 시간 초과...

for문 2개가 중첩이 되어 시간 초과인 듯 하다...

 

고민고민 하다가... 못 풀어서 chatgpt한테 물어보니...

n = int(input())

nums = list(map(int, input().split()))

result = []

stack = []

for i in range(n):
    while stack and nums[i] > nums[stack[-1]]:
        result[stack.pop()] = nums[i]
    stack.append(i)
    result.append(-1)

for r in result:
    print(r, end=' ')

이렇게 알려줬다...

 

stack리스트를 따로 만들어서... 현재까지 큰 숫자를 찾지 못한 숫자들의 인덱스를 저장해 준다!

 

그리고 -1에서 큰 숫자를 찾으면 업데이트 해주는 식의 코드인데...

 

while문이 stack이 비어있지 않거나, i번째 숫자리스트가 저장된 인덱스의 숫자리스트보다 클 때만 돌아가서...

시간이 적게 소요!

완벽하게 이해했다고는 못하겠지만 살짝은 알겠는... 그런 상황...!