[Programmers] Stack/Queue - 주식가격 (Python)

출처ㅣ Programmers 코딩테스트 고득점 Kit

Stack/Queue: 주식가격 [Lv2]

문제 설명

초 단위로 기록된 주식가격이 담긴 배열 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초간 가격이 떨어지지 않았습니다.

 

Solution

---

문제 해석

문제 설명이 나에게 너무 어려웠다. 그래서 해당 예제가 답이 왜 저렇게 나오는지, 설명을 먼저 하고 풀이를 하려고 합니다.
리스트의 인덱스는 0부터 시작, 문제에서 초는 1부터 시작하므로 헷갈릴 수 있기 때문에, 초를 0초부터 시작한다고 바꾸고 설명하겠습니다.

prices	return
[1, 2, 3, 2, 3]	[4, 3, 1, 1, 0]

0초 일 때, prices[0] = 1
0초 제외, 그 이후 남는 주식 목록: [2, 3, 2, 3]
남은 주식 목록에서 0초값(prices[0], 1)보다 작아질 때까지의 길이: 없음
0초 값보다 작아질 때가 없으므로 끝까지 유지.
유지시간: 4초

1초 일 때, prices[1] = 2
1초 제외, 그 이후 남는 주식 목록: [3, 2, 3]
남은 주식 목록에서 1초값(prices[1], 2)보다 작아질 때까지의 길이: 없음
1초 값보다 작아질 때가 없으므로 끝까지 유지.
유지시간: 3초

2초 일 때, prices[2] = 3
2초 제외, 그 이후 남는 주식 목록: [2, 3]
남은 주식 목록에서 2초값(prices[2], 3)보다 작아질 때까지의 길이: 1
여기서 2초값보다 작아지는 때는 3초이고, prices[3]은 2이다.
유지시간: 1초

3초 일 때, prices[3] = 2
3초 제외, 그 이후 남는 주식 목록: [3]
남은 주식 목록에서 3초값(prices[3], 2)보다 작아질 때까지의 길이: 없음
3초 값보다 작아질 때가 없으므로 끝까지 유지.
유지시간: 1초

4초 일 때, prices[4] = 3
4초 제외, 그 이후 남는 주식 목록: []
이 이후 남은 주식이 없으므로 이 때가 지나면 모두 끝.
유지시간: 0초

내 풀이

from collections import deque

def solution(prices):
    answer = []
    prices = deque(prices)

    while prices:
        now = prices.popleft()
        time = len(prices)
        for x in enumerate(prices):
            if x[1] < now:
                time = x[0] + 1
                break
        answer.append(time)

    return answer

Queue를 사용했다. prices를 queue로 변환하고 맨 앞의 원소를 하나씩 popleft()하여 가져온다.(now)
남은 prices에서 now보다 작은 값이 존재하는지 앞에서부터 순서대로 확인. 값이 존재한다면 time에 해당 값의 index + 1을 대입하고 for문을 빠져나온다.
만약 now보다 작은값이 존재하지 않고 for문을 모두 다 돌았다면, time은 prices의 길이를 대입한다.
time을 answer에 추가.

결과