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

문제

---

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

프로그래머스

 

• 소요 시간 : 30분
• 난이도 : LV 2

나의 풀이

---

접근 방법

현재 위치보다 뒤에 있는 리스트를 돌면서 큰 수가 나오면 멈춘다.

 

시간복잡도

O(N^2)인데, 100만 * 100만이라 무조건 시간초과가 나온다..

코드

def solution(numbers):
    answer = []
    
    # 100만
    for idx, n in enumerate(numbers):
        backs = numbers[idx+1:]

        back_bigger = -1 
        
        # 100만
        for b in backs:
            if b > n:
                back_bigger = b
                break
        
        answer.append(back_bigger)
        
        
    return answer

 

결과 : 시간초과

 

다른 사람 풀이

---

접근 방법

stack을 사용해 인덱스를 저장하고

numbers를 돌면서 현재 원소와 스택에 저장된 인덱스의 원소를 비교해 뒷큰수를 갱신해나가는 방식이다. 

 

자세한 설명은 아래 블로그에 잘 나와있다. 

https://yinq.tistory.com/187

[파이썬 PYTHON] 프로그래머스 【뒤에 있는 큰 수 찾기】

시간복잡도

for : O(N)
while : O(1) == 스택의 길이만큼 돌수 있어 O(N)이라고 착각되기 쉽다.

하지만 numbers의 모든 데이터는 1번만 push & pop할 수 있으므로 O(N) * O(1) = O(N)이다.

https://school.programmers.co.kr/questions/52564

프로그래머스

 

코드

def solution(numbers):
    n = len(numbers)
    answer = [-1] * n
    stack = []
    
    for idx in range(n):
        target = numbers[idx]
        while stack and target > numbers[stack[-1]]:
            answer[stack.pop()] = target
            
        stack.append(idx)
    
    return answer

결과 : 정답

 

정리

---

스택이라는 자료구조까진 접근할 수 있었는데

인덱스를 저장하는 것까지 생각하지 못했다. 

다시 풀어보면 좋을듯한 문제 ~