[코딩테스트] 스택/큐 - 주식가격

---

문제

 

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

프로그래머스

 

 

매초마다 갱신되는 주식 시장에서 매초 가격에 대해 몇 초나 방어했는지를 리턴하는 문제

 

문제 설명이 조금 이상해서 이해하는데 시간이 좀 걸렸다. 입출력 예에서 3초의 경우, 3에서 4초까지 넘어오는 동안 1초 방어한 것으로 보고 0이 아닌 1를 리턴한다. 따라서 마지막 초는 무조건 0이 된다.

 

 

 

문제 설명

 

---

전략

 

01. 브루트포스

 prices 리스트를 순회하면서 그 앞의 가격들이 현재 순회중인 값보다 클 경우 index끼리 비교해서 그 값을 result 리스트의 해당 index에 저장. 끝난 뒤에도 result 리스트에 비어있는 값이 있다면 마지막 index에서 해당 index 빼주기.

 

 이중 반복문으로 최악의 경우 O(n^2)의 시간 복잡도를 가진다. 사실상 모든 경우의 수를 체크하는 거라 효율이 좋지는 않을 것 같다.

 

02. 스택

 상승장일 때는 (=이전 값이 현재 값보다 작거나 같다면) 스택에 해당 값을 추가하다가  하락장이 왔다면 스택에서 값들을 하나씩 빼면서 현재 값보다 큰 값들을 체크해준다. 하락장에서 현재 값보다 큰 값은 가격 방어에 실패한 값이므로 현재 index에서 해당 index를 빼주면 가격 방어한 기간이 된다.

 

 순회가 끝난 후에 스택에 아직 값들이 남아있다면 가격 방어에 성공한 값들이므로 마지막 index에서 해당 index를 빼서 결과에 업데이트해준다.

 

 

---

풀이

 

def solution(prices):
    st = []
    result = [0] * len(prices)
    
    for i, v in enumerate(prices):
        if i < 1:
            st.append((i, v))
            continue
        
        if v >= prices[i - 1]:
            st.append((i, v))
        else:
            while len(st) != 0 and st[-1][1] > v:
                candi = st.pop()
                result[candi[0]] = i - candi[0]
            st.append((i, v))
    
    while len(st) > 0:
        candi = st.pop()
        result[candi[0]] = len(prices) - 1 - candi[0]
    
    
    return result

 스택을 이용해 풀었다.

 

 상승장일 때 값들을 저장할 스택 st과 가격 방어한 기간을 저장할 result 리스트를 만들어준다. 가격과 그 당시 기간이 중요하므로 enumerate() 함수를 이용해 prices 리스트의 인덱스와 가격을 튜플 형태로 둘다 st에 저장해준다.

 

 각 조건문에서는 기준을 현재값과 이전 값을 비교하는 것으로 잡았는데, i < 1일 경우 즉, 첫번째 가격은 st에 아무 값도 없으므로 상승장, 하락장 관계없이 스택에 추가해줬다.

 

 그 다음으로 (현재 가격) >= (이전 가격) = (상승장), (현재 가격) < (이전 가격) = (하락장) 에 따라 분기시켜줬다.

 

 하락장일 경우에 현재 가격보다 높은 이전 가격들이 여러개가 있을 수 있으므로 while을 통해 전부 처리해주었다.

 

 마지막으로 for문 순회가 끝난 이후에도 스택에 값들이 남아 있는 경우가 있다. 바로 스택에 추가된 이후로 마지막까지 가격을 방어한 경우다. 따라서 마지막 while문으로 마지막 인덱스에서 해당 인덱스를 빼준 값을 각 result에 추가해서 기간을 나타냈다.