[프로그래머스] Lv2. 주식가격

2️⃣ 주식가격

문제 설명

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

제한사항

• prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
• prices의 길이는 2 이상 100,000 이하입니다.

입출력 예

prices return

[1, 2, 3, 2, 3]

[4, 3, 1, 1, 0]

입출력 예 설명

• 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
• 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
• 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
• 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
• 5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.

※ 공지 - 2019년 2월 28일 지문이 리뉴얼되었습니다.

💡 아이디어

비슷한 문제가 자주 출제되는 것 같아서 풀어보았는데, 어려웠다.

큐와 스택 풀이법을 생각했고, 구글링의 도움을 받아서 풀었다!

✅ 전체적인 아이디어는 다음과 같다

가격을 차례대고 스택에 넣고, 스택 맨 위의 값이 새로운 가격보다 작다면 pop을 해준다.

그리고 가격의 인덱스가 pop이되는 순서가 즉, 가격이 떨어지지 않는 기간으로 볼 수 있다.

📝 풀이

큐, FIFO

prices를 모두 큐에 넣어버리고

큐가 비기 전까지 맨 앞부터 하나씩 빼서 남아있는 거와 비교를 해준다

가장 쉽고 직관적인 풀이법

from collections import deque

def solution(prices):
    answer = []
    queue = deque(prices) #주식가격을 큐에 넣는다
    
    while queue: #큐가 비기 전 까지 이를 반복한다
        sec = 0 #가격이 떨어지지 않는 시점 
        price = queue.popleft() #맨앞
        
        for q in queue: #큐 하나씩 
            sec += 1 #가격이 떨어지지 않은 시간
            if price > q: #맨앞보다 가격이 떨어지면 
                break
        answer.append(sec)
    
    return answer

스택, FILO

사실 스택을 사용한 게 더 이해하기 어려웠다

나올수 있는 가장 큰 값으로 둔 후, 값이 떨어질 경우를 찾아서 이를 수정해주는 코드다.

현재 순회하는 값이 stack의 top보다 작다면 pop하고 인덱스를 변경해준다

def solution(prices):
    #모든 가격을 max값으로 세팅해준다
    answer = [i for i in range(len(prices) -1, -1, -1)] 
    stack = [0]  
    #값이 떨어지는 시점을 찾아 수정해준다    
    for i in range(1, len(prices)):
        while stack and prices[stack[-1]] > prices[i]:
            tmp = stack.pop() #pop 
            answer[tmp] = i - tmp
        stack.append(i)
    
    return answer

❗ 느낀점

아이디어를 떠올리는 게 생각보다 너무 어렵다.