[Python]스택/큐: 주식가격

문제 설명

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

내 코드

def solution(prices):
    answer = [0 for i in range(len(prices))]
    for i in range(len(prices)):
        for j in range(i + 1, len(prices)):
            answer[i] += 1
            if prices[i] > prices[j]:
                break
    return answer

간단하게 생각해서 이중 for 문으로 해결하였다. 먼저 prices의 길이가 더 길어질 수 있으므로 리스트 컴프리헨션(list comprehension)으로 모든 값이 0 인 answer 리스트를 만들었다.(지금 생각하면 defaultlist로 만들어도 됐을 것 같다.) 그 후 가격이 하락하면 answer에 1을 더하는 것을 중지하는 형식으로 짰다.

정확성 테스트
테스트 1 〉 통과 (0.01ms, 10.1MB)
테스트 2 〉 통과 (0.08ms, 10.2MB)
테스트 3 〉 통과 (1.15ms, 10.3MB)
테스트 4 〉 통과 (1.27ms, 10.2MB)
테스트 5 〉 통과 (1.49ms, 10.3MB)
테스트 6 〉 통과 (0.05ms, 10.2MB)
테스트 7 〉 통과 (0.74ms, 10.3MB)
테스트 8 〉 통과 (0.92ms, 10.3MB)
테스트 9 〉 통과 (0.05ms, 10.2MB)
테스트 10 〉 통과 (1.47ms, 10.2MB)

효율성 테스트
테스트 1 〉 통과 (145.75ms, 18.7MB)
테스트 2 〉 통과 (120.04ms, 17.7MB)
테스트 3 〉 통과 (191.83ms, 19.5MB)
테스트 4 〉 통과 (139.06ms, 18.3MB)
테스트 5 〉 통과 (92.72ms, 17.1MB)

채점 결과
정확성: 66.7
효율성: 33.3
합계: 100.0 / 100.0

사실 이 문제를 고민하면서 가장 많이 생각한 점이 O(n^2)이 되는 점이였다. 왠지 이중 for문을 돌리면 시간 초과가 될 줄 알았다. 하지만 다른 사람들도 이 부분을 고민해봤지만 해결하진 못한 것 같다.

다른 사람의 생각

from collections import deque
def solution(prices):
    answer = []
    prices = deque(prices)
    while prices:
        c = prices.popleft()

        count = 0
        for i in prices:
            if c > i:
                count += 1
                break
            count += 1

        answer.append(count)

    return answer

collections에서 deque를 가져와서 짠 코드로 while 문을 통해 prices 내의 값들을 가져와서 가격이 떨어지기 전까지 1씩 더하고 떨어지면 1을 더하고 for 문을 끝내는 형태이다.