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

'프로그래머스 - 주식가격'

문제 설명

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

제한사항

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

prices
[1, 2, 3, 2, 3]

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

입출력 예 설명

• 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
• 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
• 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
• 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
• 5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.
  
  
  
  

✔ My Solution

---

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

✅ 각 prices 리스트에 있는 데이터를 체크하기 위한 반복문 구현

• prices[i]의 다음 값 [i+1] 을 조견연산을 하기 위한 내부 반복문 구현
• prices[i] 와 prices[j]를 비교할 때마다 cnt += 1
• pirce[i] 가 prices[j] 보다 작을 때 내부 반복문이 멈추고 answer 리스트의 cnt 를 push

다른사람 풀이

---

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

✅ answer [] = prices 의 길이만큼 0으로 된 리스트를 만든다

• 나의 풀이처럼 cnt 변수가 따로 필요 없다
• 자바에서 array를 만드는 방법이라 비슷해서 참고가 되었다

int[] answer = new int[prices.length] 

✔ Solution - Stack

---

Jasvascript를 공부하면서 알고리즘 구조를 구체적으로 모르는 상태에서 문제를 풀다보디 출제의도를 벗어난 것 같아서 스택을 사용하여 문제를 풀 수 있는 방법을 찾아봤다.


code

def solution(prices):
    answer = [0]*len(prices)
    stack = []

    for i in range(len(prices)):
        
        while stack and prices[stack[-1]] > prices[i]:
            j = stack.pop()
            answer[j] = i - j
        
        stack.append(i)
        
    while stack:
        j = stack.pop()
        answer[j] = len(prices) - j - 1
    
    return answer

step 1

def solution(prices):
    answer = [0]*len(prices)
    stack = []
    
#   prices = [1,2,3,2,3]
#   stack =  [0,1,2,3,4]
#   answer = [0,0,0,0,0]

    for i in range(len(prices)):
        stack.append(i)
    
    return answer

step 2

def solution(prices):
    answer = [0 for _ in range(len(prices))]
    stack = []
    
#   prices = [1,2,3,2,3]    
#   stack =  [0,1,3,4]
#   answer = [0,0,1,0,0]

    for i in range(len(prices)):
        
        while stack and prices[stack[-1]] > prices[i]:
            j = stack.pop()
            answer[j] = i - j
            
            
        stack.append(i)
    
    return answer

while stack and prices[stack[-1]] > prices[i]:

• stack 이 비어있지 않을 때 (stack.append[i]가 최소 한 번 이상 진행되었을 때)
• prices[stack[-1]] = [0,1,2,3,4] 순으로 진행됨
• prices[stack[-1]] > prices[i] 가 참인 경우는 가격이 감소되었을 때를 의미

j = stack.pop()
answer[j] = i - j

✅ j = stack.pop()

• stack 은 가격이 안떨어진 시간들의 모은
• 가격이 줄어든 시점은 stack에서 빠진다.

✅ answer[j] = i - j

• answer 리스트에 줄어든 시점의 위치의 1을 추가한다

👀 가격이 떨어지는 시점

---

• 예시 리스트에선 i = 3 일 때 처음이자 마지막으로 떨어진다
• prices[i] = 2
• prices[stack[-1]] = prices[ i - 1 ] = 3

• 3 > 2
  • POP!
  • stack = [0,1,4,5]
• j 는 stack의 마지막 = 가격이 떨어지기 직전의 값/ 위치 == 2
• answer[j] = i - j
  • answer[2] = 3 - 2 == 1
  • answer = [0,0,1,0,0]

   while stack:

       #   stack =  [0,1,3,4]
       #   answer = [0,0,1,0,0]

       j = stack.pop()
       answer[j] = (len(prices) - 1)  - j

나머저 시간 위치의 초 계산 = 가격이 안떨어졌기 때문에 [i] 에서 [-1]위치까지의 count 계산

answer[4] = ( 5 - 1 ) - 4 == 0
answer[3] = ( 5 - 1 ) - 3 == 1
answer[1] = ( 5 - 1 ) - 1 == 3
answer[0] = ( 5 - 1 ) - 0 == 4
[4, 3, 1, 1, 0]