[백준 17298] 오큰수 (Gold 4)

문제

[백준] 오큰수 (Gold 4)

요약

• A(i)의 오큰수는 오른쪽에 있으면서 A(i)보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다.
• 그러한 수가 없으면, 오큰수는 -1이 된다.

분류

• 스택

풀이

1. 스택

• 일반적인 풀이는 아닌 듯하다.
• 다음과 같은 규칙을 갖는다.
  1. 가장 오른쪽에 있는 수의 오큰수는 반드시 -1 이므로, answer 의 초깃값은 -1이다.
  2. 스택이 비어있으면, 주어진 수열의 가장 오른쪽 수를 추가한다.
  3. 수열의 오른쪽에서 두 번째 있는 수를 스택의 가장 위에 있는 수와 비교한다.
     1. 수열의 수가 더 작으면 : 스택의 가장 위에 있던 수를 answer 에 추가하고, 수열의 수를 스택에 쌓는다.
     2. 수열의 수가 더 크면 : 스택 가장 위의 수와 수열의 수를 비교해서, 수열의 수가 더 작아질 때까지 pop한다. 만약 수열의 수보다 더 큰 수가 남으면, 더 큰 수를 answer 에 append. 스택에 아무것도 남지 않으면 answer 에 -1 append.

n = int(input())
arr = list(map(int, input().split()[::-1]))

answer = [-1]
stack = []

for num in arr:
  if not stack:
    stack.append(num)
    continue
  elif stack[-1] <= num:
    while stack and stack[-1] <= num:
      stack.pop()
    if not stack:
      answer.append(-1)
    else:
      answer.append(stack[-1])
    stack.append(num)
  elif stack[-1] > num:
    answer.append(stack[-1])
    stack.append(num)

for val in answer[::-1]:
  print(val, end=" ")