[프로그래머스] 스택/큐 - 주식가격 (Python 풀이)

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

코딩테스트 연습 - 주식가격

 

의문.... 

def solution(prices):
    
    answer = [0 for a in range(len(prices))]
    
    for i in range(len(prices)):
        for j  in range(i+1, len(prices)):
            answer[i] += 1
            if prices[i] > prices[j]:
                break
        
    return answer

이게... 왜 스택/큐 문제일까요.....?

이중반복문으로 풀면 정확성 테스트와 효율성 테스트 모두 잘 통과한다.

스택/큐를 사용해서 풀면 더 효율적인가?

 

 

해결!

친구의 도움을 얻어서 출제 의도에 맞는 것 같은 풀이법을 얻었다.

스택에서 꺼낸 값(인덱스)과 반복문 현재 위치에 있는 값의 주식 가격을 비교한다.

for문을 돌고있는 i가 현재 시간이라고 생각하면 된다.

 

비교하는 과정에서 스택에서 꺼낸 값보다 현재 시점의 주식 가격이 떨어졌다면, 

현재 시점과 스택에서 꺼낸 값의 차를 저장한다.

 

주식 가격이 떨어지지 않았다면,

지금까지 스택에 남아있는 값은 현재 시점까지 계속 오르고 있다는 말이다.

스택에서 값을 꺼내지 않고 다음 위치로 넘어간다!

 

이 풀이에서 핵심은 (시간의 흐름대로) 반복문을 계속 진행하면서

현재 시점보다 가격이 높은 시점이 언제였는지 되짚어가면서 판단하는 방식이다.

가격이 떨어진 시점이 이미 결정된 경우에는 스택에서 제거되므로 더이상 비교하지 않아도 되는 장점이 있다.

최악의 경우, 이중반복문을 사용하는 것 처럼 n^2일테지만

최선일 경우 2n만으로 충분하다!!

프로그래머스에서 코드를 돌려보니 확실히 수행시간이 절반정도로 줄었다 굿굿

내친구... 똑똑하다......

 

def solution(prices):
    # answer = 몇초 후 가격이 떨어지는지 저장하는 배열
    answer = [len(prices)-i-1 for i in range(len(prices))]
    
    # stack = prices의 인덱스를 차례로 담아두는 배열
    stack = [0]
    
    for i in range(1, len(prices)):
        while stack:
            index = stack[-1]
            
            # 주식 가격이 떨어졌다면
            if prices[index] > prices[i]:
                answer[index] = i - index
                stack.pop()
            
            # 떨어지지 않았다면 다음 시점으로 넘어감 (주식 가격이 계속 증가하고 있다는 말)
            else:
                break
        
        # 스택에 추가한다.
        # 다음 시점으로 넘어갔을 때 다시 비교 대상이 될 예정이다.
        stack.append(i)
        
    return answer