.programmers(주식가격)

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

 

1. 2022.04.08 시도

소요시간:  49분

import java.util.*;

class PriceTag {
    int index;
    int price;
    
    PriceTag(int index, int price) {
        this.index = index;
        this.price = price;
    }
    
    public String toString() {
        return "("+index+":"+price+")";
    }
}

class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        
        PriorityQueue<PriceTag> pq = new PriorityQueue<>((o1,o2) -> {
            if (o1.price < o2.price) {
                return 1;
            } else if ( o1.price > o2.price) {
                return -1;
            }
            return 0;
        });
        pq.offer(new PriceTag(0, prices[0]));
        for (int i=1; i<prices.length; i++) {
            while(pq.size() > 0 && pq.peek().price > prices[i]) {
                PriceTag priceTag = pq.poll();
                answer[priceTag.index] = i - priceTag.index;
            }
            pq.offer(new PriceTag(i, prices[i]));
        }
        
        while(!pq.isEmpty()) {
            PriceTag priceTag = pq.poll();
            answer[priceTag.index] = (prices.length-1) - priceTag.index;
        }
        
        return answer;
    }
}

풀이 접근 과정

PriorityQueue에서 가장 큰 수가 앞으로 나오도록 세팅한다.

그리고 가장 큰수를 peek로 가져오고 현재 가격하고 비교한다. 만약 비교해서 더 크다면 이전껄 꺼내와서 기간을 매겨준다.

그걸 계속 반복한다.

마지막 while은 이제 남은 것들을 마지막 인덱스 값(prices.length-1)에서 차이를 계산해서 넣어준다.

 

느낀점

• 처음에는 아래처럼 단순하게 풀었더니 시간이 오버되어 실패했다.

// 단순하게
import java.util.*;

class Solution {
    public int[] solution(int[] prices) {
        Set<Integer> end = new HashSet<>();
        int[] answer = new int[prices.length];
        for (int i=0; i<prices.length; i++) {
            for (int j=0; j<i; j++) {
                if (end.contains(j) == false) {
                    if (prices[j] <=prices[i]) {
                        answer[j]++;
                    } else {
                        answer[j]++;
                        end.add(j);
                    }
                }
            }
        }
        
        return answer;
    }
}

• PriorityQueue를 이용해서 풀때, 문제를 오해한 부분(가격이 동일할때보다 기간을 정산하는 줄 알았음)이 있었고 pq.size()를 하지않아 런타임에러가 나는 경우도 있었다.

---

알고리즘 정리노트: .leetcode(알고리즘 문제풀이 접근)

반응형