[알고리즘]STEP1-1주차 스택/큐(주식가격)

👼🏻복습링크

주식가격

https://programmers.co.kr/learn/courses/30/lessons/42584

1️⃣ 첫번째 풀이(통과X)

❗ 시간초과로 효율성 테스트를 통과하지 못했음
👉🏻 파이썬에선 pop(0)은 O(n)의 시간복잡도를 가지므로 큐를 구현하기엔 효율성 측면에서 불리하다

def solution(prices):
    answer = []
    
    while(1):
        temp=0
        if len(prices)==0:
            break
        for i in range(len(prices)):
            temp=i
            if prices[0]>prices[i]:
                break
        answer.append(temp)
        prices.pop(0)
    return answer

1. prices list를 Queue에 대한 연산으로 이용함
2. while문
   • temp를 기본값 0으로 설정 : temp는 가격이 떨어지지 않은 시간을 의미
   • prices의 길이가 0이 되면 break
   • for 문을 실행
   • answer에 temp를 저장
   • prices.pop(0)을 하여 prices의 첫 번째 원소를 pop 함
3. while 문 내부의 for문
   • prices의 길이만큼 반복
   • temp 값에 i를 대입 : i가 경과된 시간을 의미.
   • prices[0]보다 큰 prices[i]가 발생하면 for문을 break
   • prices[i]가 없었다면 temp는 len(prices)가 됨

2️⃣ 두 번째 풀이

❗ deque 이용 : deque의 popleft()는 O(1)의 시간복잡도를 가져 pop(0)에 비하여 효율성 측면에서 유리

from collections import deque
#dequq 생성
deq=deque()
#기존의 리스트를 deque로 바꾸기
prices=deque(prices)
prices.popleft()
prices.popright()

#통과한 코드
from collections import deque
def solution(prices):
    answer = []
    prices=deque(prices)
    
    while(1):
        temp=0
        if len(prices)==0:
            break
        for i in prices:
            if prices[0]>i:
                temp=prices.index(i)
                break
            temp=len(prices)-1
        answer.append(temp)
        prices.popleft()
        
    return answer

1. price를 deque로 변환
2. while 문
   • prices의 길이가 0이 될 때까지 반복
   • temp=0으로 선언. temp는 주식 가격이 떨어지지 않은 시간을 의미
   • for문을 통해 구해진 temp를 answer.append(temp)
   • prices.popleft()를 통해 prices의 첫 번째 원소를 pop
3. for 문
   • prices[0]과 prices의 다른 원소들의 값을 비교
   • price[0]의 값이 더 크다면 해당 원소의 index 값을 temp로 저장 후 break
   • 모든 원소가 prices[0]보다 크거나 같으면 len(prices)-1 시간만큼 가격이 떨어지지 않았으므로 temp에 len(prices)-1 값을 저장

3️⃣ 세번째 풀이

❗ 두 번째 풀이와 비슷하지만 enumerate 활용하고 효율성 테스트에서 더 좋은 결과를 냄

from collections import deque

def solution(prices):
    answer = []
    prices=deque(prices)
    
    while(1):
        if len(prices)==0:
            break
        else:
            temp=prices.popleft()
            value=0
            for i, j in enumerate(prices):
                if temp>j:
                    value=i+1
                    break
                value=len(prices)
            answer.append(value)
    return answer

1. price를 deque로 변환
2. while 문
   • prices의 길이가 0이 될 때까지 반복
   • prices.popleft()의 값을 temp에 저장
   • value를 0으로 선언. value는 가격이 떨어지지 않은 시간을 의미
   • for문을 통해 구해진 value를 answer.append(value)
3. enumerate for 문
   • i는 인덱스 값, j는 원소 값을 의미.
   • temp와 j값을 비교 후 temp가 더 크면 value에 i+1을 저장 후 break
   • 모든 원소가 temp보다 크거나 같으면 len(prices) 시간만큼 가격이 떨어지지 않았으므로 value에 len(prices) 값을 저장