TIL (2022.02.26)

➕ 오늘 푼 문제

프로그래머스 - 주식가격

➕ 아이디어

핵심 아이디어는 스택에 (현재 값을 기준으로) 값이 떨어지지 않은 주식의 인덱스를 저장하는 것이다. 매 반복마다 현재 값보다 큰 주식이 있다면, 즉 가격이 떨어진 주식이 있다면 스택에서 제거하며 정답을 갱신해준다.

• 각 주식이 가질 수 있는 최대 기간으로 초기화한다.
• prices를 1번째 원소부터 탐색하며, 이전 원소의 인덱스를 스택에 넣는다
• 스택 top을 확인하며, 현재 값보다 크다면 가격이 떨어진 경우이므로 최대 기간을 갱신한다.
  • 이때 최대 기간은 현재 인덱스 - 가격이 떨어진 경우의 인덱스(=스택 top 값) 이다.

➕ Java 코드

import java.util.*;

class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        Stack<Integer> stack = new Stack<Integer>();
        
        for(int i=0; i<prices.length; i++){
            answer[i] = prices.length-1-i;
        }
        
        for(int i=1; i<prices.length; i++){
            stack.push(i-1);
            while(!stack.isEmpty() && prices[stack.peek()] > prices[i]){               
                int j = stack.pop();
                answer[j] = i-j;
            }
        }
        
        return answer;
    }
}

➕ Python 코드

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

➕ 궁금한 내용 및 소감

• 스택을 사용하겠다고 마음을 먹고서도 구현 방법이 딱 떠오르지 않아 꽤 오랜 시간 고민한 문제다. 어떤 값이 연속되고 특정 경우에만 변경이 된다면 스택을 활용하는 것도 고려해봐야겠다. 다른 사람들의 풀이는 어떤 지도 한번 확인해 보면 좋을 것 같다.

➕ 참고 문헌

• 없음