[lvl2]뒤에 있는 큰 수 찾기

문제 설명:

정수로 이루어진 배열 numbers가 있습니다. 배열 의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 뒷 큰수라고 합니다.

정수 배열 numbers가 매개변수로 주어질 때, 모든 원소에 대한 뒷 큰수들을 차례로 담은 배열을 return 하도록 solution 함수를 완성해주세요. 단, 뒷 큰수가 존재하지 않는 원소는 -1을 담습니다.

제한사항

4 ≤ numbers의 길이 ≤ 1,000,000
- 1 ≤ numbers[i] ≤ 1,000,000

입출력 예

numbers	result
[2, 3, 3, 5]	[3, 5, 5, -1]
[9, 1, 5, 3, 6, 2]	[-1, 5, 6, 6, -1, -1]

입출력 예 설명

입출력 예 #1

2의 뒷 큰수는 3입니다. 첫 번째 3의 뒷 큰수는 5입니다. 두 번째 3 또한 마찬가지입니다. 5는 뒷 큰수가 없으므로 -1입니다. 위 수들을 차례대로 배열에 담으면 [3, 5, 5, -1]이 됩니다.

입출력 예 #2

9는 뒷 큰수가 없으므로 -1입니다. 1의 뒷 큰수는 5이며, 5와 3의 뒷 큰수는 6입니다. 6과 2는 뒷 큰수가 없으므로 -1입니다. 위 수들을 차례대로 배열에 담으면 [-1, 5, 6, 6, -1, -1]이 됩니다.

코드:

  
def solution(numbers):
    stack = []
    result = [-1] * len(numbers)

    for i, num in enumerate(numbers):
        while stack and numbers[stack[-1]] < num:
            result[stack.pop()] = num
        stack.append(i)

    return result

코드 설명:

문제의 요구사항인 “뒷 큰수”를 효율적으로 찾기 위해 스택을 사용
- 이전 수들의 인덱스를 저장하는 용도
numbers 리스트를 순회하며, 현재 원소가 스택의 마지막 보다 큰 경우, 스택에서 원소를 제거하고 해당 위치에 현재 원소를 뒷 큰수로 바꿔주고 현재 원소의 인덱스를 스택에 추가

시도1:

테스트 케이스는 모두 통과했지만 체점 시 시간 오류 떴던 코드

enumerate로 인덱스를 찾고 그 기반으로 슬라이싱을 이용하여 진행했다

  
def solution(numbers):
  answer = []
  for idx, number in enumerate(numbers):
      if max(numbers[idx:]) == number:
          answer.append(-1)
      for n in numbers[idx:]:
          if n>number: 
              answer.append(n)
              break
  return answer

시도 2:

deque를 사용하고, 기존 슬라이싱 기법에서 popleft()를 사용했다
기존 코드에 비해 효율성이 좋아지긴 했지만, 아직 부족하다..

  
from collections import deque

def solution(numbers):
    answer = []
    numbers = deque(numbers)
    while numbers:
        n1 = numbers.popleft()
        result = -1
        for i in numbers:
            if i > n1:
                result = i
                break
        answer.append(result)
    return answer

우수답변자 코드:

defaultdict를 사용하고 이중 for문으로 순회

  
from collections import defaultdict
def solution(numbers):
    answer = [-1]*len(numbers)
    for i in range(len(numbers)-1,-1,-1):
        for j in range(i-1,-1,-1):
            if numbers[j] >= numbers[i]:    break
            answer[j] = numbers[i]
    return answer

우수답변자2 코드:

나와 비슷하게 스택을 사용하였다

  
def solution(numbers):
  answer = [-1 for _ in numbers]

  stack = []
  for i in range(len(numbers)-1):
      stack.append(i)
      if numbers[i] < numbers[i+1]:
          while stack and numbers[stack[-1]] < numbers[i+1]:
              answer[stack.pop()] = numbers[i+1]

  return answer