[Python] 코딩테스트 고득점Kit | 스택큐4 - 주식가격

아래의 문제는 프로그래머스 코딩테스트 고득점 Kit 내용이며 코드는 직접 푼 내용입니다.

---

주식가격

문제상황 및 요구사항

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

---

풀이과정

아무래도 나는 코딩이 정말 안맞는걸까.....정말 쉬운건데.. for문으로 하면..

커서(?)처럼 하나씩 비교해나간다고 생각하면 이중포문을 돌려볼 수 있다. 

그래서 if prices[i]<=prices[j]: 부분은 계속 가격이 오르는 상태 즉, 가격이 떨어지지 않는 기간을 계속 더하는 거고, 

가격이 떨어지게 되면 break가 되는 것이다.

결과

이중for문식으로도 가능하지만, FOR문을 두번 돌아서 시간복잡도가 O(N^2)

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

 

배운점

• range()와 enumerate() 시간복잡도차이 :
  range는 O(1)인데, enumerate()는 반복자료형 내 원소를 하나하나 봐야해서 O(n)다 
• 이중 for문의 시간복잡도 : prices리스트의 길이만큼 for문을 두번 돌아서 시간복잡도가 O(N^2)
• 너무 오래걸린다......취지에 맞게 스택이나 큐로 푼 방법을 찾아봐야한다.

---

참고 

참고한 블로그 링크

https://huidea.tistory.com/19

[프로그래머스][stack/queue] 주식가격 python (200722)