프로그래머스 코딩테스트 연습 - [스택/큐] - 주식가격

(문제)

초 단위로 기록된 주식 가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

제한사항

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

입출력 예pricesreturn

[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 in range(len(prices)):
        cnt = 0
        for j in range(i + 1, len(prices)):
            if prices[i] <= prices[j]:
                cnt += 1
            else:
                cnt += 1
                break
        answer.append(cnt)
    return answer

 

하지만, 스택을 이용하여 좀 더 기발하고 빠른 속도를 가지고도 풀 수 있습니다.

 

예시를 기준으로 설명을 합니다.

[1, 2, 3, 2, 3]

값들의 나열을 순회하면서 해당 index를 스택에 넣는 과정을 거칩니다.

stack에 넣으면서 스택에 가장 위에 부분을 비교 체크를 합니다

다음 price와 비교하면서 prices가 낮아진다면 해당 index로 prices가 낮아지지 않는 구간을 ans에 추가하면서 예외 처리하면서 stack에 넣으면 순회를 한 번 거친 stack은 이제 prcies들이 높아지는 값들만 존재하는 index 모음입니다.

stack을 팝 하면서 최대길이 - 해당 인덱스를 answer에 넣어주면 답이 됩니다.

글로는 이해하기 힘들 겁니다. 아래의 그림이 첨가된 설명을 참고하고 다시 보시거나 코드를 보시는 걸 추천합니다.

 

그림 - 스택을 이용한 풀이 설명

[ 코드 ]

 

# 주식 가격 - 풀이 2 (스택 이용)
def solution(prices):
    answer = [0] * len(prices)
    s = []

    for i, price in enumerate(prices):
        # 값이 바로 낮아지는 순간 예외 처리
        while s and price < prices[s[-1]]:
            j = s.pop()
            answer[j] = i - j
        s.append(i)

    # s에는 계속 높아지는 price들의 index모음이다 고로 최대길이에서 index 값을 빼주면 답이 된다.
    while s:
        j = s.pop()
        answer[j] = len(prices) - 1 - j

    return answer


prices = [1, 2, 3, 2, 3]
sol = solution(prices)
print(sol)

 

---

후기

 

스택으 이용해서 문제 푸는 방법은 첫 브루트 포스로 문제를 풀고 나서

다른 사람의 코드를 참고하였는데

스택을 이용한 풀이에 익숙해지면 이 풀이도 쉽게 떠올랐으면 좋겠다.