[프로그래머스] 주식 가격 (python3)

스택/큐

📝 문제

문제 설명

초 단위로 기록된 주식가격이 담긴 배열 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 = []
    
    for i, price_1 in enumerate(prices) :
        answer.append(len(prices)-i-1)
        for j, price_2 in enumerate(prices[i:]) :
            if price_2 < price_1 :
                answer[-1] = j
                break
    return answer

1. enumerate를 이용해 차례대로 비교
   첫번째 원소는 두번째~마지막 원소랑 비교
   두번째 원소는 세번째~마지막 원소랑 비교
   ... 이런식으로 비교함
2. answer에 가격이 떨어지지 않았을 때의 값을 미리 넣어두고, 만약 가격이 떨어졌을 경우 answer[-1]을 이용하여 갱신해줌

정확성 테스트는 모두 통과했으나 효율성 테스트는 싹 다 불통과..

🔗 다른 사람의 풀이

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

내 풀이와 비슷한 원리이긴 하나 enumerate 대신 range를 이용하여 직접 인덱싱 해줌

이 풀이에서 배워갈 것

1. enumerate()는 반복 자료형 내 원소를 하나씩 다 봐야하니까 O(n) 인 반면, range()는 O(1) - 시간복잡도 신경 쓸 것