17298 오큰수 (Python)

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

import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))
stack=[]
# 오른쪽에서 왼쪽으로 쭉 진행한다
for i in range(N-1,-1,-1):
    n = A[i]
    # 오큰수랑 비교해서 원래 수열에선 오큰수로 기록해버린 다음
    noks = True
    for j in range(len(stack)-1,-1,-1):
        if stack[j] > n:
            noks = False
            A[i] = stack[j]
            break
    if noks:
        A[i] = -1
    # 스택에서 자기보다 약하거나 같은 놈들 다 죽여버린다
    while(len(stack)>1 and stack[-1] <= n):
        stack.pop()
    # 스택에 냅다 넣는다
    stack.append(n)

    # 스택 맨 위 peek하면 그게 오큰수
for a in A:
    print(a,end=' ')

 

내가 접근했었던 방향 

 

오른쪽에서 왼쪽으로 순회하며 오른쪽에 있는 정보들을 저장함.
이는 곧 '오큰수가 될 수 있는 수'들의 집합임.

오큰수를 찾으려면 그 집합을 탐색해야 함.

최적화를 위해 불필요한 연산을 없앨 수 있음.

불필요한 연산이라 함은, 511116 <- 이런 수열이 있다면
중간에 있는 1111은 탐색하지 않아도 되는데 탐색해버린다는 것.

 

'오큰수가 될 수 있는 수'에 숫자를 넣을 때마다
자신보다 작거나 같은 수들을 삭제하면 됨.
배열의 맨 끝 값을 삭제하므로 삭제 연산의 비용도 작다.

 

 

N = int(input())
seq = list(map(int, input().split()))
stack = []
res = [-1] * N

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

print(res)

 

다른 사람들이 접근했었던 방향

 

코드 출처

 

왼쪽에서 오른쪽으로 순회하며 왼쪽에 있는 정보들을 저장함.

이는 곧 '오큰수를 찾고 싶은 수'들의 집합임.

 

오른쪽으로 갈 때마다 만나는 숫자(정보)들은
'오큰수가 될 수 있는 수'임.

 

'오큰수를 찾고 싶은 수'들의 집합을 탐색하며
'오큰수가 될 수 있는 수'보다 작거나 같은지 확인함.
오큰수가 되었다면 결과를 저장하고 집합에서 삭제하면 됨.

 

오큰수를 찾기 위해선, 왼쪽에 있는 정보들 중에서 필요한 것이 2가지가 있음.

1. 오큰수를 찾고 싶은 숫자들이 어디에 있었는지 (결과 저장해야 하니까)
2. 오큰수를 찾고 싶은 숫자들의 값은 얼마였는지 (비교해야 하니까)

이를 위해선 1. 인덱스만 저장하면 됨.
배열에 arr[i] 이런 식으로 접근하면 2. 도 알 수 있기 때문임.