[Python] 프로그래머스 Lv2_뒤에 있는 큰 수 찾기

https://school.programmers.co.kr/learn/courses/30/lessons/154539

프로그래머스

 

• 정수로 이루어진 배열 numbers가 있음
• 배열의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 뒷 큰수라고 함
• 정수 배열 numbers가 매개변수로 주어질 때, 모든 원소에 대한 뒷 큰수들을 차례로 담은 배열을 return
• 단, 뒷 큰수가 존재하지 않는 원소는 -1을 담음

제한사항

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

 

"""
입출력 예시)

numbers = [2, 3, 3, 5] -> [3, 5, 5, -1]
numbers = [9, 1, 5, 3, 6, 2] -> [-1, 5, 6, 6, -1, -1]
"""

 

 

## 의사코드 ##

# deque 이용
# q = deque((i, v) for i, v in enumerate(numbers))

# answer의 초기값을 -1로 설정
# answer = [-1] * len(numbers)

# while q:
#     idx, num = q.popleft()
#     for i, n in q:
#         현재 원소(num)보다 가장 가까이 있으면서 큰 수가 있으면 현재 원소의 인덱스에 해당하는 answer 값을 n으로 변경
#         if n > num:
#             answer[idx] = n
#             break

 

 

 

첫 번째 시도

 

from collections import deque
def solution(numbers):
    answer = [-1] * len(numbers)
    q = deque((i, v) for i, v in enumerate(numbers))
    while q:
        idx, num = q.popleft()
        for i, n in q:
            if n > num:
                answer[idx] = n
                break          
    return answer

 

 

-> 추가 테스트케이스 실패 (시간 초과)

 

 

질문하기에서 어떤 분이 레벨2 문제인 주식가격 문제와 유사하다고 하신 것을 보고

주식가격 문제 풀이와 비슷하게 deque를 활용해서 풀었는데 시간 초과로 실패했다. 

 

https://monzheld.tistory.com/96

[Python] 프로그래머스 Lv2_주식가격

 

 

• 과정 확인

numbers = [2, 3, 3, 5]

"""
num: 2
idx: 0 

n: 3
i: 1 

n > num
n: 3
수정된 answer[idx]: 3
------------------------------
num: 3
idx: 1 

n: 3
i: 2 

n: 5
i: 3 

n > num
n: 5
수정된 answer[idx]: 5
------------------------------
num: 3
idx: 2 

n: 5
i: 3 

n > num
n: 5
수정된 answer[idx]: 5
------------------------------
num: 5
idx: 3 

[3, 5, 5, -1]

"""

 

 

 

통과한 코드

 

def solution(numbers):
    answer = [-1] * len(numbers)
    stack = []
    for i, n in enumerate(numbers):
        # 현재 숫자가 이전 인덱스의 값보다 크면 answer의 이전 인덱스 값을 현재 숫자로 변경
        while stack and numbers[stack[-1]] < n:
            answer[stack.pop()] = n
        # 스택에 현재 숫자의 인덱스 저장 
        stack.append(i)
    return answer

 

 

-> stack 활용으로 시간 초과 없이 통과

 

 

• 과정 확인

numbers = [2, 3, 3, 5]

"""
n: 2
i: 0 

stack: [0] 

n: 3
i: 1 

numbers[stack[-1]] < n
stack[-1]: 0
numbers[stack[-1]]: 2
answer[stack.pop()]: 3
------------------------------
stack: [1] 

n: 3
i: 2 

stack: [1, 2] 

n: 5
i: 3 

numbers[stack[-1]] < n
stack[-1]: 2
numbers[stack[-1]]: 3
answer[stack.pop()]: 5
------------------------------
numbers[stack[-1]] < n
stack[-1]: 1
numbers[stack[-1]]: 3
answer[stack.pop()]: 5
------------------------------
stack: [3] 

[3, 5, 5, -1]
"""

 

 

 

 

 

참고)

 

https://only-wanna.tistory.com/entry/Python-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%92%A4%EC%97%90-%EC%9E%88%EB%8A%94-%ED%81%B0-%EC%88%98-%EC%B0%BE%EA%B8%B0-%ED%92%80%EC%9D%B4

[Python] 프로그래머스 뒤에 있는 큰 수 찾기 풀이