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

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

📝 문제

 

🚫 제한 사항

 

✏️ 입출력

 

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

 

💡 풀이

자신보다 크면서 가까이 있는 수를 answer에 저장해야 한다. 

numbers의 마지막 수는 비교 대상이 없으므로 result의 마지막은 항상 -1이 될 것이다. 

처음에는 이중 for문을 사용해 풀었다. 시간초과 가 발생했다. 아무래도 제한 사항에서 numbers와 numbers[i]의 크기를 크게 잡아서 그런 것 같다. 

이후, 해결한 방법은 stack을 사용했다. 

stack의 top을 numbers[i]와 비교해서 결과를 answer에 갱신하도록 했다. 

 

 

1. 숫자들을 저장할 스택 생성, answer 리스트 -1로 초기화

2. numbers의 길이만큼 반복문

3. while문 -> 스택에 요소가 존재하고, 스택의 top에 있는 인덱스에 해당하는 숫자가 현재 순회 중인 숫자보다 작을 때까지 반복

4. 더 큰 숫자를 발견하면 answer 갱신

 

 

def solution(numbers):
    stack = []  # 숫자들을 저장할 스택
    answer = [-1] * len(numbers)  # 결과 리스트를 -1로 초기화
    
    for i in range(len(numbers)):
        while stack and numbers[stack[-1]] < numbers[i]:
            answer[stack.pop()] = numbers[i]  # 더 큰 숫자를 발견하면 스택에서 팝하며 결과를 갱신
        
        stack.append(i)  # 현재 인덱스를 스택에 추가
    
    return answer