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

(문제) 주식가격 (스택/큐)

---

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

입력설명

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

prices의 길이는 2 이상 100,000 이하입니다.

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

출력설명

가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성

테스트케이스

입력예제	출력예제
[1, 2, 3, 2, 3]	[4, 3, 1, 1, 0]
[3, 2, 1, 2, 5, 4, 1, 3, 1]	[1, 1, 6, 3, 1, 1, 2, 1, 0]

---

해결방법

인덱스 0은 1초 시점 / 인덱스 1은 2초 시점 / 인덱스 3은 3초 시점 …..

[중요] 생각을 할 때, 1초간!!! 이라는 단어를 잘 생각해야한다.

이 1초간이라는 의미는 1초에 1원일때 만약 2초는 0원이 되면 1초간은 떨어지지 않았기 때문에 + 1이 되는 것이다.

1초 후에는 떨어지는 것이지만 1초간이기 때문에 떨어지는 것이 아니다.

인덱스 0 (1초) : 가격이 떨어지지 않는 경우

시작은 1초 시점(인덱스0)에서 시작하면 1초 자체는 그대로 이므로 + 1은 무조건 한다.
그다음 2초 시점(인덱스1)에서 자기보다 작지않으면 + 1 한다.
그다음 3초 시점(인덱스2)에서 자기보다 작지않으면 + 1 한다.
…. 반복한다.

인덱스 2 (3초) : 다음 초에 가격이 떨어짐

시작은 3초 시점(인덱스2)에서 시작하면 일단 자기 자신 초는 작지않기 때문에 + 1을 한다. (1초간은 안 떨어지기 때문에)
그다음 4초 시점(인덱스3)에서 자기보다 작아지므로 끝낸다.

인덱스 3 (4초) : 다음 초가 끝

4초에서 ~ 5초까지 1초간 떨어지지 않고, 5초 다음은 없으니 +1만 되고 끝난다.

---

코드

from collections import deque

arr = deque([3, 2, 1, 2, 5, 4, 1, 3, 1])
answer = []

while True:
    if not arr:
        break
    cnt = 0
    current = arr.popleft()
    # 마지막에 리스트 안에 값이 없으면 반복문은 안한다.
    for x in arr:
        # 1초간 즉 자신의 시간 포함
        if current > x:
            print(arr)
            cnt = cnt + 1
            break
        cnt = cnt + 1
    answer.append(cnt)

print(answer)