[프로그래머스 lv2]주식가격

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

프로그래머스

 

문제설명

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

 

제한사항

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

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

 

입출력 예

prices    return

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

 

입출력 예 설명

1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.

2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.

3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.

4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.

5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.

문제 해결 방법

아 이문제는 참 어렵다! 시간 복잡도는 O(N^2)에 맞추면 안되고 O(NlogN)까지 가능하다. 

그런데 이 문제 아무리생각해봐도 O(NlogN)로 풀기 어려웠다. 그래서 O(N^2)로 풀어봤는데,,, 끝이 안난다. 

이조건 맞추면 저 조건 안맞고, 저 조건 맞추면 이 조건 안맞고 그랬다. 

 

그래서 결국 답을 보고 이해했다. 

 

이 문제는 효율성을 해결하기 위해서는 반드시 스택으로 풀어야한다. 그런데 이 문제 스택을 어디에 적용할지 떠올리기가 참 어렵다. 

 

코드 주석으로 설명하였다. 

 

코드 구현

 

기존 코드 - 미해결

def solution(prices):
    #O(N)으로 구현
    answer = []
    
    prices=list(prices)
    stackk=[]
    newPrices=[]
    newPrices = list(prices)

    for i in range(len(prices)):
        
        if i == 0:
            stackk.append(prices[i])
        else:
            
            newPrices.reverse()
            if len(newPrices)==0:
                break
            
            newPrices.pop()
            newPrices.reverse()
            cnt=0

            #print('prices[i]', prices[i-1], 'newPrices', newPrices)
            for price in newPrices:
                #print('price', price)
                if prices[i-1]<=price:
                     cnt+=1
            
            answer.append(cnt)
            
    answer.append(0)  
    #print(answer)
    
    
    
    return answer

 

개선 코드 - 해결

 

def solution(prices):
    answer = []
    total = len(prices)
    answer = [0] * total
    #각 초 시점의 길이를 넣을 배열
    stackk = [0] 

    # 스택을 0으로 초기화 한 이유는 순회를 인덱스 1부터 하기 위해서임 
    # prices의 0번 인덱스는 스택에 넣고 시작한다. 
    
    for i in range(1, total):
        # 1부터 total까지 순회한다. 
        # 0번 인덱스부터 total 인덱스까지 순회할 때, 가격의 증가만 있다면,
        # 계속 stackk에 넣는다. 
        # 만약 가격이 떨어진다면 그때부터는 스택에서 꺼내어서 하락한 가격의 인덱스로부터 길이를 구한다. 
        while stackk and prices[stackk[-1]]>prices[i]:
            a=stackk.pop()
            answer[a]=i-a
        stackk.append(i)
        
    while stackk: # 스택이 빌 때까지 순회하여 길이를 찾아준다. 
    #이 스택은 최종적으로 증가한 값들만 남아있다. 
        a=stackk.pop()
        answer[a]=total-a-1
        
    #print(answer)
    
    return answer

 

시간/공간 복잡도

O(NlogN)

최적화 및 개선

많은 개선을 했다. 음 로직을 아예 뜯어고침 

어려웠던 점/느낀점

답지를 안보고 혼자 코드 로직을 생각할 수 있을때 까지 연습하는것 까지 했다. 

다음에 또 풀때는 잘 풀었으면 좋겠다.