[프로그래머스 Level2] 주식 가격 Python, JavaScript

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

문제 설명

prices 가 이런식으로 주어지고 [1, 2, 3, 2, 3]
각각의 index 가격들이 얼마 뒤에 가격이 떨어졌는지를 알아내면 된다. 안 떨어졌다면 끝까지 갔을 때의 시간을 출력한다.
답은 [4, 3, 1, 1, 0]이 된다.
0번째 index인 1의 값은 끝까지 가격이 떨어지지 않았으니 4 - 0 인 4
1번째 index인 2도 끝까지 가격이 떨어지지 않았으니 4 - 1 인 3
2번째 index인 3은 다음 index에서 가격이 떨어졌으니 3 - 2인 1
3번째 index인 2는 끝까지 가격이 떨어지지 않았으니 4- 3 인 1
마지막 index는 가격이 떨어질 수 없으니 0 이 된다.

문제 풀이

가장 쉬운 방법은 역시 2중 for문으로 푸는 방법이다. 하지만 2중 for문으로 푼다면 시간 복잡도가 많이 증가하게 된다. 그래서 오래걸린다...

2중 for문 코드

def solution(prices):
    answer = []
    for i in range(len(prices)-1): # 마지막 전까지 ,, 마지막에는 비교할 수 없이 그냥 0이기에
        count = 0
        for j in range(i+1, len(prices)): # 마지막까지.
            if(j == len(prices) - 1 or prices[i] > prices[j]): # 끝날 때 답에 count + 1 해준 값을 넣고 끝낸다.
                answer.append(count+1)
                break
            else : 
                count +=1
    answer += [0] # 마지막 요소는 비교할 것도 없이 그냥 내려가고 그런게 없으니 0을 더해줌.
    return answer

Stack을 이용해서는 앞서 푼 LeetCode처럼 해주면 되고 이 문제는 아까 문제와는 다르게 마지막까지 떨어지지 않으면 떨어지지 얼만큼 떨어지지 않았는지 출력해야 하므로 stack이 빌 때까지 while문을 실행해서 갱신해준다.

Stack을 이용한 코드

def solution1(prices):
    answer = [0 for _ in range(len(prices))]
    stack = []
    for i in range(len(prices)):
        while len(stack) != 0 and prices[i] < prices[stack[len(stack) -1]]:
            temp = stack.pop()
            answer[temp] = i - temp
        stack.append(i)
    while len(stack):
        temp = stack.pop()
        answer[temp] = len(prices) - temp - 1

    return answer

JS로는 문제를 풀 수 없지만 그래도 풀어보는게 좋을 것 같아서 코드를 짜봤다. Python이랑 크게 다를 것 없다.

js Stack 코드

function solution(prices) {
    let answer = new Array(prices.length).fill(0);
    let stack = [];
    let length = prices.length;
    for(let i = 0; i < length; i++) {
        while(stack.length && prices[i] < prices[stack[stack.length - 1]]) {
            let temp = stack.pop();
            answer[temp] = i - temp;
        }
        stack.push(i)
    }
    while(stack.length) {
        let temp = stack.pop();
        answer[temp] = length - temp - 1;
    }
    return answer;
}