[문제풀이 py] B17298 오큰수

오큰수 / 스택 🥞

---

  🎠. '스택(Stack)'에 값이 아닌 '인덱스(index)'를 넣어 문제를 해결할 줄 알아야 한다.

[시간초과 난 코드.py]

  N = int(input())
  stack = list(map(int, input().split()))
  # print(stack)

  len = len(stack)
  res = []
  ano_stack = []

  for i in range(len):
      # print("res:", res)
      cur = stack.pop()
      # print("cur:", cur)
      if i == 0:
          res.append(-1)
          ano_stack.insert(0, cur)
          continue
      # print("ano_stack", ano_stack)
      flag = 0
      for ele in ano_stack:
          # print("ele:", ele)
          if ele > cur:
              flag = 1
              res.append(ele)
              break
      if flag == 0:
          res.append(-1)
      ano_stack.insert(0, cur)
  res = res[::-1]

  for ele in res:
      print(ele, end=" ")

🤡. 실수한 부분
: stack의 길이는 최대 백만까지 갈 수 있다.
ano_stack의 길이도 최대 백만까지 갈 수 있다.
이를, 이중 for문을 돌리니 시간초과난다.

  N = int(input())
  list = list(map(int, input().split()))
  # print(stack)

  res = [-1] * len(list)

  stack = []
  for i in range(N):
      cur = list[i]
      while stack and cur > list[stack[-1]]:
          res[stack.pop()] = cur
      stack.append(i)
  print(*res)

💡. 문제 접근 방법
: list 오른쪽부터 하나씩 스택에 넣어서,
다시 스택에서 마지막으로 넣은 원소부터 pop()하면서
현재값과 스택안에 들어있는 값을 일일이 비교해서
현재값보다 큰값이 스택안에 없으면 res 리스트에 -1을 넣는 방식으로 문제를 해결하려 했으나,
이런면 시간초과가 난다.

🧩암기: 인덱스 스택
인덱스를 스택에 넣고 스택의 최신 인덱스(stack[-1])에 해당하는 값과 현재값을 비교하여,
현재값이 크면, 최신 인덱스를 스택에서 pop()하고, 그 인덱스에 해당하는 값을 현재의 값으로 바꿔준다.