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

프로그래머스 - [Level 2] 주식가격 

프로그래머스

---

문제 분석

 

• 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 반환해라.

---

해결 키 포인트

 

• 우선순위 큐 사용
• 인덱스와 가격을 가지고 있을 클래스 구현 (Node)
  • 비교 시, 가격이 큰 것부터 우선순위를 갖도록 구현
  • 가격이 같을 경우 인덱스가 작은 것부터 우선순위를 갖도록 구현
• 큐에 넣기 전 큐 확인(자신보다 큰 가격이 있을 경우 반복), 큐에 삽입
  • 현재 가장 앞에 있는 Node의 가격이 현재 가격보다 클 경우, 추출 후 결과 등록
• 마지막 인덱스까지 추가한 후, 큐에 남아있는 노드 모두 추출

---

코드

 

import java.util.PriorityQueue;
import java.util.Queue;

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

        Queue<Node> queue = new PriorityQueue<>();

        for (int i = 0; i < prices.length; i++) {
            while (!queue.isEmpty() && queue.peek().price > prices[i]) {
                Node value = queue.poll();
                answer[value.index] = i - value.index;
            }
            queue.add(new Node(prices[i],i));
        }

        while(!queue.isEmpty()) {
            Node value = queue.poll();
            answer[value.index] = prices.length - 1 - value.index;
        }

        return answer;
    }

    public static class Node implements Comparable<Node> {
        int price;
        int index;
        public Node(int price, int index) {
            this.price = price;
            this.index = index;
        }

        @Override
        public int compareTo(Node o) {
            if(price == o.price) {
                return index - o.index;
            }
            return o.price - price;
        }
    }
}