뒤에 있는 큰 수 찾기
문제 설명
정수로 이루어진 배열 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]이 됩니다.
HOW
사고 과정
numbers의 최대 길이가 1,000,000이므로 numbers를 앞에서부터 완전탐색하면 최악의 경우 시간초과가 나게 됩니다. 어차피 뒤에 숫자 중 가장 가까우면서 현재 숫자보다 큰 수를 찾는 것이기 때문에 뒤에서 부터 해도 문제가 없겠다고 생각했습니다. 그래도 여전히 완전탐색은 루프가 너무 많기 때문에 같은 작업을 반복하지 않도록 코드를 작성해 루프를 최대한 줄여줘야했습니다.
첫 발상은 다음과 같습니다.
가장 큰 수만 가지고 있고 그 수보다 현재 수가 크다면 -1을 저장하고 아니라면 가장 큰 수를 업데이트 해주면 된다.
- 정답 배열에 -1을
numbers의 길이만큼 채운다. - 맨 뒤부터 돌며 가장 큰수를 저장한다.
- 그 수와 현재 수를 비교하며 현재 숫자가 더 크다면 넘어가고(이미 -1이 저장되어 있음) backnum을 현재 숫자로 변경한다.
- 가장 큰 수가 더 크다면(
numbers[i]< backnum) 그 수를 정답 배열에 넣는다.(answer[i] = backnum)
→ 문제점 발생 : 현재 숫자(numbers[i+1]) 부터 가장 큰 수(backnum) 사이에 현재 숫자보다 더 큰 수가 있을 경우 그 숫자를 answer에 넣어야 함
→ 해결 : backnum이 업데이트 되지 않았을 때 그 값들을 저장할 queue(temp)를 운영해 queue의 값들과 현재 숫자를 비교한다
→ 문제점2 발생 : 솔루션 코드에서는 queue를 popleft로 값을 호출해 비교하고 있다. (현재 값보다 작은 값들은 더 이상 queue에 존재해도 의미가 없기 때문)
→ 다음 라인에서 등호를 넣지 않았을 때
if (numbers[i] > backnum)
[10, 2, 20, 3, 30, 4, 1, 20, 30] 이와 같이 배열안에 최대값과 동일한 값이 들어오면 queue에서 비교하며 모든 원소를 pop한다. 따라서 그 앞으로는 어떤 값도 업데이트 될 수 없다.
→ if (numbers[i] >= backnum) 등호 추가
정리
- 뒤에부터 탐색하며 backnum에 가장 큰 수를 queue에 backnum부터 현재 인덱스까지의 숫자들을 넣는다.
- 현재숫자와 backnum과 비교하여 backnum보다 크다면 answer에 -1을 넣는다
- backnum보다 현재 숫자가 작다면 queue를 순회하며 현재 숫자보다 더 큰수를 찾는다. 그리고 그 수를 answer에 넣는다.
솔루션 코드
#https://school.programmers.co.kr/learn/courses/30/lessons/154539
from collections import deque
def solution(numbers):
# 배열 길이 저장
length = len(numbers)
# 정답 배열
answer = [-1] * length
# 뒷수 중 가장 큰 수
backnum = numbers[-1]
# 뒷수 중 가장 큰 수가 변경되지 않았을 때 저장 배열
temp = deque([backnum])
for i in range(length - 2, -1, -1):
# 뒷수가 존재하지 않을 때 = 뒷수중 가장 큰 수가 현재 숫자보다 작거나 같을 때
if (numbers[i] >= backnum):
# 뒷수중 가장 큰 수(backnum)를 현재 숫자로 변경
backnum = numbers[i]
# temp 큐 초기화
temp = deque([backnum])
# 뒷 수가 존재할 때 = 뒷수 중 가장 큰 수 > 현재 숫자
else:
# 큐를 돌면서
while (temp):
# 가장 가까운 수부터 확인 (현재 숫자보다 작다면 pop이므로 제거된다)
v = temp.popleft()
# 현재 숫자보다 크다면
if (v > numbers[i]):
# 정답 배열에 추가
answer[i] = v
# pop이기 때문에 다시 큐에 넣어준다
temp.appendleft(v)
temp.appendleft(numbers[i])
# break를 걸지 않으면 while(queue)이기 때문에 무한 루프
break
return answer