문제

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

제한 사항

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

풀이

아이디어

• 이중 반복문을 사용하되, 바로바로 끝낼 수 있는건 빨리 종료시킨다.
  • 현재 아이템이 prices의 마지막 아이템이라면 무조건 0을 answer 배열에 넣어준다.
  • 현재 가격이 다음 가격보다 작다면, 무조건 1을 answer 배열에 넣어준다.
• 다음 가격이 현재 가격 이상이라면, 다음 내부 반복문을 실행한다.
  • 현재 가격(cur)를 저장해놓고, iter라는 새로운 반복문을 돌 인덱스를 만들어서 cur보다 작은 값을 만날 때까지 iter와 duration을 증가시키면서 돈다.
  • 주의) 만약 현재 가격보다 작은 값을 만나지 못해서 배열 prices 끝까지 갔을 때는 duration을 반환해주고, 아니라면 duration + 1을 반환해준다. (while문의 조건을 내가 그렇게 짜서..)

코드

function solution(prices) {
    let answer = Array(prices.length).fill(0);
    
    for(let i=0; i<prices.length; i++) {
        let cur = prices[i];
        
        //마지막 가격인 경우
        if(i === prices.length - 1) {
            answer[i] = 0;
            break;
        }
        
        //다음가격이 현재가격 이상인 경우
        if(cur <= prices[i+1]) {
            let iter = i+1;
            let duration = 0;
            while(cur <= prices[iter] && iter < prices.length) {
                duration++;
                iter++;
            }
            answer[i] = iter === prices.length ? duration : duration + 1;
        }
        
        //다음거가 현재가격 미만인 경우
        else if(cur > prices[i+1]){
            answer[i] = 1;
        }
    }
    
    return answer;
}

파이썬 코드 (큐)

• 이건 근데 O(N^2)이라서 여기선 운좋게 통과했지만 실제 코테에선 사용하면 안될듯

from collections import deque

def solution(prices):
    answer = []
    deq = deque(prices)
    
    while len(deq):
        cur = deq.popleft()
        # 남은 deq에서 현재보다 작은 값이 나오면 시간을 세다가 answer에 넣는다.
        time = 0
        for p in deq:
            time += 1
            if(p < cur):
                break
        
        answer.append(time)
        time = 0

    return answer

파이썬 코드 (스택)

• 다시 생각해낸 O(N) 풀이이다. 스택을 활용한다.
• prices 리스트를 순회하면서, 특정 조건에 해당하지 않는 한 계속 stack에 자신의 인덱스와 가격을 저장한다. 특정 조건은 아래와 같다.
  • stack의 길이가 0보다 크고, stack의 마지막원소가 현재 price보다 클 때
  • 해당 조건을 만족하는동안 계속 stack에서 pop을 해서 answer에 원하는 형태로 저장한다. (현재 index - pop한 원소의 인덱스)
• 마지막에 stack에 남아있는 것들은 끝까지 가격이 떨어지지 않은 것들이므로, len(prices) - pop_i - 1을 해서 모두 해소시켜준다.

def solution(prices):
    stack = []
    answer = [-1 for _ in range(len(prices))]
    for i, price in enumerate(prices):
        while stack and price < stack[-1][0]:
            pop_price, pop_i = stack.pop()
            answer[pop_i] = i - pop_i
        stack.append([price, i])
    
    #마지막에 남은 stack들 해소해주기
    for s in stack:
        pop_price, pop_i = s
        answer[pop_i] = len(prices) - pop_i - 1
        
    return answer