[백준] 17298번(오큰수)

백준 17298번

내가 작성한 코드(시간초과)

def get_maxvalue(n, array):
  for i in range(n, len(array)):
    if array[i] > arr[n-1]:
      return arr[i]
  return -1
  
n = int(input())
arr = list(map(int, input().split()))

result = []
for i in range(n-1):
  result.append(str(get_maxvalue(i+1, arr)))
        
result.append(str(-1))
print(*result)

◼ for문 중첩으로 문제 풀이

• 시간초과
  .

다른 사람이 작성한 코드

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

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

print(*result)

출처

.
◼ 스택을 활용한 문제 풀이

❓ stack에 원소를 인덱스로 갖는 원소가 [2, 4]인데 arr[i] == 3이면 어떡하지? 2는 arr[i]보다 작은데 제거되지 못하잖아!

• stack에 인덱스가 저장된 원소들은 사실상 내림차순으로 정렬된 상태
• stack에 인덱스가 저장된 원소가 차례로 [2, 4]일 수는 없다. 2는 while문에서 3에 의해 stack[0]은 제거되기 때문!
• stack[1]은 arr[stack[0]] > arr[1]일 때만 생긴다.
• stack[2]는 arr[stack[1]] > arr[2]일 때만 생긴다.
  ⇒ pop되는 원소보다 아래 있는(먼저 들어온) 원소를 인덱스로 하는 arr 값은 arr[stack.pop()]보다 작을 수 없다.
  (편의를 위해 stack 인덱스 사용해서 설명)