[Python] 프로그래머스, 주식가격 Lv.2 (feat. collections deque, stack, 파이썬)

반짝반짝 알고리즘, 인프준

 

 

 

 

 

 

주식가격

문제 링크

프로그래머스

 

 

문제 설명

*공식 문제 지문이 잘 이해되지 않아서 잘 정리해 주신 분의 재해석을 참고했습니다. (@programmers camel-master님)

 

n초 간의 주가를 초 단위로 기록한 배열 prices가 매개변수로 주어질 때, 각  초의 주가를 기준으로 해당 초부터 n초 사이에 가격이 떨어지지 않은 시간은 몇 초인지 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

 

 

제한 조건

prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.

prices의 길이 n은 2 이상 100,000 이하입니다.

 

 

입출력 예

prices	return
[ 1, 2, 3, 2, 3 ]	[ 4, 3, 1, 1, 0 ]

 

 

입출력 예 설명

 

1. 1초의 주가는 1이며 1초부터 5초까지 총 4초간 주가를 유지했습니다.

 

2. 2초의 주가는 2이며 2초부터 5초까지 총 3초간 주가를 유지했습니다.

 

3. 3초의 주가는 3이며 4초의 주가는 2로 주가가 떨어졌지만 3초에서 4초가 되기 직전까지인 1초간 주가를 유지된 것으로 봅니다. 따라서 5초까지 총 1초간 주가를 유지했습니다.

 

4. 4초의 주가는 2이며 4초부터 5초까지 총 1초간 주가를 유지했습니다.

 

5. 5초의 주가는 3이며 5초 이후로는 데이터가 없으므로 총 0초간 주가를 유지했습니다.

 

 

 

 

해결 과정

이 문제는 프로그래머스 코딩테스트 고득점 kit, 스택 / 큐 문제에 포함되어 있습니다. 따라서 스택 또는 큐를 활용해서 문제를 풀어보려고 접근했습니다.

 

1. 결괏값 result와 prices를 queue로 변환하여 선언해 주었습니다.

 

2. queue에서 하나씩 빼서 비교할 예정이므로, queue가 비어있을 때까지 while loop을 돌려주었습니다.

 

3. 가격이 떨어지지 않은 기간 period, 주식 개장 후 첫 가격을 추출한 price를 선언해 주었습니다.

 

4. 추출한 price와 미래 주가가 담긴 나머지 queue를 비교해 주며 떨어지지 않은 기간을 1씩 증가시켜 줍니다.

 

5. for loop은 미래에 가격이 떨어졌다면 break로 종료하고 그렇지 않으면 주식이 마감될 때까지 진행됩니다.

 

6. 차례대로 결괏값에 append 해주고 모든 가격에 대해 확인을 마치면 반환해 줍니다.

 

 

제출 코드 ( Queue, FIFO )

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               # 결과값 반환

 

 

 

 

 

또 다른 풀이 ( Stack, LIFO )

def solution(prices):
    length = len(prices)
    # 모든 가격 max값으로 세팅
    result = [ 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()
            result[j] = i - j
        stack.append(i)
    return result

 

 

위 코드는 미리 결괏값을 최대 기간으로 세팅해 두고 주식 가격이 떨어진 경우를 찾아 수정하는 코드입니다. 두 문제 모두 스택과 큐에 대해 이해하고 활용해 보기 좋아 보여 한 줄씩 이해해 보기를 추천드립니다.

 

 

 

 

 

 

 

---

 

 

 

 

 

 

 

출처: 프로그래머스 코딩 테스트 연습,https://school.programmers.co.kr/learn/challenges