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

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

프로그래머스

 

처음에는 적절하게 자료구조를 사용할 생각을 못했다.

레벨 1을 싹쓸이하고 올라오느라 미처 고민도 못해봤는데,

그러다 보니 아래와 같은 코드를 먼저 시도해보았다. 딱 머릿속에 생각나는 대로..

 

def solution(numbers):
    answer = []
    for i in range(len(numbers)):
        found = False
        for j in range(i + 1, len(numbers)):
            if numbers[j] > numbers[i]:
                answer.append(numbers[j])
                found = True
                break
        if not found:
            answer.append(-1)
    return answer

 

나름 Flag 특성을 이용해서 정답을 맞추는 데까지는 성공했지만..

 

끔찍한 시간이 나왔다. 대략 시간복잡도가 O(n^2)이라 꽤나 시간을 먹겠다고 생각은 했는데, 다소 깐깐하게 시간 제약을 넣은 걸 보니 역시 레벨 2구나 싶었다.

 

그래서 자료구조적으로 고민해 보았을 때 스택밖에 가능성이 안 보여서 스택으로 한 다섯 번의 실패를 겪은 끝에..

아래와 같은 스택 풀이를 짜내었다.

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

 

훨씬 시간복잡도가 낮아진 결과를 볼 수 있었다.

확실히 스택을 잘 적용하니.. 생각보다 결과가 간단해서 놀랐다.

스택을 확실하게 이해하게 된 문제라 업로드해보았다. 실습해보고 싶다면 이 문제 강추

---

 

스택에 자신감이 생겨서 스택 관련 문제를 하나 더 풀어보았다.

Lv.2 주식가격

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

프로그래머스

 

이 문제의 경우에도 코드가 거의 비슷해서, 적절히 로직만 수정하여 EZ하게 풀 수 있었다.

while문을 한 번에 완성하는 것이 핵심이지 않을까..

 

def solution(prices):
    n = len(prices)
    result = [0] * n
    stack = []

    for i in range(n):
        while stack and prices[stack[-1]] > prices[i]:
            # 스택에서 빼내어 해당 기간 동안 가격이 떨어지지 않음을 업데이트
            j = stack.pop()
            result[j] = i - j
        
        stack.append(i)
    
    while stack:
        j = stack.pop()
        result[j] = n - 1 - j
    
    return result

 

---

 

문제 마구 풀다 보니 어느새 만 등에서 여기까지 상승

뿌듯하지만 아직 다른 사람의 풀이 보면 참 배울 게 많다.. 열심히 공부하자