주식 가격 (프로그래머스) JAVA

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

프로그래머스

문제 설명

문제 설명이 약간 애매합니다.

• 1초에 가격에서 앞으로 5초 동안 떨어지지 않으므로 4입니다
• 2초 시점에 2의 가격은 앞으로 2보다 떨어진 가격이 없으므로 3입니다.
• 3초 시점에 3의 가격은 바로 1초 후에 떨어지므로 1입니다.
• 4초 시점은 1초 후까지 가격이 떨어지지 않습니다.

 

문제에 대한 아이디어

제일 처음 생각은 뒤에서 부터 값을 추가해 그 때 제일 낮은 숫자의 인덱스를 가지고 있으면 되지 않을 까 생각했습니다.

예를 들어 3번째 인덱스 3 시점에서 지금 우선 순위 큐에 2와 3이 들어 있으면 제일 낮은 숫자의 인덱스를 현재 인덱스에서 빼는 것입니다. 하지만 이럴 경우 문제점이 있습니다.   

[1, 2, 3, 2, 3, 1] 경우를 생각해보면 3번째 인덱스 3일 때 제일 낮은 숫자는 마지막 인덱스인 1입니다. 그래서 결과가 4가 나옵니다. 하지만 바로 1초후 가격이 떨어지므로 1이여야 합니다.

 

해결책

그래서 생각한 방법은 Deque에 앞에서 부터 가격을 넣습니다. 그리고 현재 덱의 마지막 인덱스의 가격이 prices의 가격보다 크다면 가격이 떨어지는 것이므로 체크 해주면 됩니다.

  while(!dq.isEmpty() && prices[dq.getLast()] > prices[i]){
         int index = dq.removeLast();
         answer[index] = i - index; 
}

 

1 2 3 2 3에서 i가 3일 때 prices[i] 는 2이고 덱의 마지막 index는 2이름 prices[dq.getLast()]는 3입니다.

이 때 answer[index] = 1 이 저장되는 것 입니다.

그리고 현재 i 3의 덱에 뒤에 추가해 다음꺼와 비교하는 것입니다.

prices의 모든 인덱스를 살펴본후 가격이 떨어지지 않은 것은 덱에 남아 있게 됩니다. 그러므로 덱을 한번 더 돌면서 index값을 세팅해줍니다.

while(!dq.isEmpty()){
     int index = dq.removeLast();
     answer[index] = prices.length - index - 1;
}

 

전체 코드

import java.util.*;

class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        Deque<Integer> dq = new ArrayDeque<>();
        for(int i = 0; i < prices.length; ++i){
            while(!dq.isEmpty() && prices[dq.getLast()] > prices[i]){
                int index = dq.removeLast();
                answer[index] = i - index; 
            }
                
            dq.addLast(i);
        
        }
        while(!dq.isEmpty()){
            int index = dq.removeLast();
            answer[index] = prices.length - index - 1;
        }
        return answer;
    }
}