[Python] 프로그래머스 lv.2 주식가격

알고리즘 고득점 kit - 스택/큐 - lv 2

 

문제 분석

• 초마다 기록된 주식 가격이 담긴 배열 prices
• 가격이 떨어지지 않은 기간은 몇 초인지 return

 

정답 코드

다른 사람 코드 1 - deque

from collections import deque


def solution(prices):
    result = []  # 결과값
    queue = deque(prices)  # 주식가격 queue

    while queue:  # queue가 빈값이 아니면 while loop
        period = 0  # 가격이 떨어지지 않은 기간
        price = queue.popleft()  # i번째 주식 가격 추출

        for after in queue:  # 미래의 가격 목록
            period += 1  # 가격이 떨어지지 않은 기간 + 1초
            if price > after:  # 미래에 가격이 떨어졌다면
                break  # break
        result.append(period)  # 유지된 기간 결과값에 저장

    return result  # 결과값 반환

 

다른 사람 코드 2 - stack

def solution(prices):
    length = len(prices)
    answer = [i for i in range(length - 1, -1, -1)]

    stack = [0]
    for i in range(1, length, 1):
        while stack and prices[stack[-1]] > prices[i]:
            j = stack.pop()
            answer[j] = i - j
        stack.append(i)
    return answer

 

다른 사람 코드 3 - stack

def solution(prices):
    stack = []
    answer = [0] * len(prices)
    for i in range(len(prices)):
        if stack != []:
            while stack != [] and stack[-1][1] > prices[i]:
                past, _ = stack.pop()
                answer[past] = i - past
        stack.append([i, prices[i]])
    for i, s in stack:
        answer[i] = len(prices) - 1 - i
    return answer

 

2회차 - 2024.11.27

문제 분석

• 초단위로 기록된 주식 가격이 담긴 배열 prices
• 가격이 떨어지지 않은 기간은 몇 초인지 return
• 가격이 떨어지지 않는다 == 가격이 오른거나 같다
• 가격이 떨어지는 순간 기간 세기 끝

 

코드 설계

• 각 가격이 끝날 때 까지 몇초간 떨어지는지 확인
• 리스트의 특정 값을 이후 리스트의 값과 모두 비교
• 이중 for문으로 하나하나씩 비교? → 시간초과 (효율성 문제)

 

정답 코드

1차 - 실패..

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

 

다른 사람 코드 1 - 클론 코딩

from collections import deque

def solution(prices):
    answer = []
    q = deque(prices)

    while q :
        period = 0 # 가격이 떨어지지 않은 기간
        price = q.popleft() # i번째 주식 가격 추출

        for after in q : # 미래의 가격 목록
            period += 1 # 다음 미래의 가격과 비교하는 순간 시간 +1
            if after < period : # 가격이 떨어지면
                break
        answer.append(period)
    return answer