[PGM] 주식 가격 (Java)

문제링크

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

코딩테스트 연습 - 주식가격

문제풀이

👨🏻‍💻 핵심 스킬 👨🏻‍💻
 우선순위 큐

1. 문제 이해

초 단위로 기록되어있는 주식의 가격에 대한 정보가 들어있는 int형 배열이 input으로 들어올 때 그 가격이 떨어지지 않은 기간이 몇 초인지 return 하는 문제이다.

 

2. 접근방법

우선순위 큐를 활용하여 문제를 해결할 수 있다. 우선 순위 큐를 사용하면 Heap처럼 사용할 수 있다.

주식 가격과 그 주식이 입력된 초를 가지는 객체를 생성하여 문제를 해결해줄 수 있다.

Max Heap의 구조로 만들어주어 해당 Queue에서 값이 가장 큰 값들만 빼서 확인해주면 문제를 쉽게 해결할 수 있다.

구현코드

package pgm_42584;

import java.util.PriorityQueue;

public class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];

        PriorityQueue<Price> maxHeap = new PriorityQueue<>();
        for(int i = 0; i< prices.length; i++){
            Price inputPrice = new Price(i, prices[i]);
            maxHeap.add(inputPrice);
            while (!maxHeap.isEmpty() && maxHeap.peek().value > inputPrice.value){
                Price removePrice = maxHeap.remove();
                answer[removePrice.idx] = inputPrice.idx - removePrice.idx;
            }
        }

        while (!maxHeap.isEmpty()){
            Price removePrice = maxHeap.remove();
            answer[removePrice.idx] = prices.length - removePrice.idx-1;
        }
        return answer;
    }

    public class Price implements Comparable<Price> {
        int idx;
        int value;

        public Price(int i, int p){
            idx = i;
            value = p;
        }

        @Override
        public int compareTo(Price o) {
            return o.value == this.value ? 0 : o.value > this.value ? 1 : -1;
        }
    }
}

잘못된 지식이나 궁금한 내용이 있을 경우 편하게 댓글 남겨주시면 감사하겠습니다 :)