[알고리즘] 프로그래머스 - 주식가격(Python)

코딩테스트 연습 - 주식가격 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

* 문제 설명

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

* 제한사항

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

* 입출력 예

prices = [1, 2, 3, 2, 3]

return = [4, 3, 1, 1, 0]

* 입출력 예 설명

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

* 풀이

문제 지문이 난해하여 이해하는 데에 30분이 넘게 걸렸다.  단순히 가격이 떨어지지 않은 기간이 몇초인지 구하라는 말만 있었기에 주식을 잘 하지 않는 필자는 가격이 떨어지지 않은 기간이 무엇을 의미하는지 알 수가 없었다. 그러다가 프로그래머스의 질문 검색을 보고 이해하게 되었다. 먼저 입출력 예시에서 [1, 2, 3, 2, 3]을 보면, 첫 원소 1을 기준으로 나머지 원소들을 바라보자. [2, 3, 2, 3]인데, 1을 제외한 모든 원소가 1보다 크므로 가격이 떨어지는 구간은 없다고 할 수 있다. 따라서 1초~ 5초까지 가격이 떨어지지 않았으므로, 4가 return된다. 두번째 원소 2를 기준으로 했을 때, [3, 2, 3]의 원소들 모두 2보다 크거나 같으므로, 가격이 떨어진 구간이 없다. 따라서 2초 ~ 5초이므로, 3이 return된다. 세번째 원소 3을 기준으로 했을 때, [2, 3]에서 3 -> 2 가격이 떨어졌으므로, 3초에서 4초 소요되었을 때의 간격, 즉 1초간 가격이 떨어지지 않은 것으로 간주한다(1을 return). 4번째 원소 2를 기준으로 하였을 때, [3]의 원소는 2보다 크므로 가격이 떨어진 구간이 없다. 그러므로 4초 ~ 5초의 간격이 존재한다(1을 return). 마지막 원소 3은 다음 원소가 존재하지 않으므로 0을 return하면 된다. 리스트의 원소를 왼쪽부터 하나씩 pop하여 나머지 원소들과 비교를 하면 되므로, 자료구조 queue를 이용하면 쉽게 문제를 풀 수 있다. 브루트 포스 알고리즘을 통해 풀 수도 있지만 queue로 푸는 것이 시간복잡도상 더 빠르다.  다음은 풀이 코드이다.

from collections import deque

def solution(prices):
    answer = []
    queue = deque(prices)
    
    while queue :
        pop_data = queue.popleft()
        cnt = 0
        
        for i in queue :
            if pop_data > i :
                cnt += 1
                break
            
            cnt += 1
            
        answer.append(cnt)
        
    return answer