[프로그래머스] 138477번 - 명예의 전당 (1) [Java]

프로그래머스

 

 

---

 

 

문제

 

 

제출한 코드

import java.util.*;

class Solution {
    public int[] solution(int k, int[] score) {

        int[] result = new int[score.length];
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        for (int i = 0; i < score.length; i++) {
            pq.add(score[i]);
            if (pq.size() > k) pq.poll();
            result[i] = pq.peek();
        }

        return result;
    }
}

 

 

풀이

처음에는 List를 사용해서 아래와 같이 제출했었다. 이후 다른 사람들의 풀이를 보니 PriorityQueue 를 사용한 풀이가 있어서 찾아봤다.

List를 사용한 방식은 Priority Queue 방식 이후에 설명한다.

 

PriorityQueue 는 우선순위 큐로, 들어간 순서에 상관 없이 일정한 규칙에 따라 우선순위를 정하고, 우선순위가 가장 높은 데이터가 가장 먼저 나오게 된다. Default 값으로는 가장 낮은 수가 우선순위를 가지게 된다.

 

따라서 결과값을 반환할 int 배열 result와, 명예의 전당을 PriorityQueue로 선언한 후,

for문을 통해 코드를 진행했다.

핵심 코드는 아래와 같다.

for (int i = 0; i < score.length; i++) {
    pq.add(score[i]);
    if (pq.size() > k) pq.poll();
    result[i] = pq.peek();
}

 

해당 문제에서 사용한 메서드는 add(), size(), poll(), peak() 이다.

• add(): 삽입에 성공하면 true 를 반환한다. 실패 시 IllegalstateException이 발생된다.
• size(): 현재 큐에 있는 요소의 개수를 반환한다.
• poll(): 큐에서 객체를 꺼내서 반환한다.
• peak(): 삭제 없이 요소를 읽어온다.

 

먼저 pq.add() 로 우선순위 큐에 현재 score 값을 삽입해준다.

이때 우선순위 큐의 성질에 따라 가장 왼쪽에 있는 수보다 작으면 왼쪽으로 삽입되고, 가장 오른쪽에 있는 수보다 크면 오른쪽으로 삽입된다.

이후 size 를 k와 비교하여, 만약 수용하는 범위인 k보다 해당 큐의 크기가 더 크면 pq.poll() 을 통해서 가장 왼쪽에 있는 수(가장 작은 수)가 큐에서 삭제되면서 반환된다.

마지막으로 pq.peek() 을 통해, 삭제 없이 반환된 가장 작은 수를 result 배열에 저장해주었다.

 

처음에 제출한 방식인 List를 이용한 코드는 아래와 같다.

import java.util.*;

class Solution {
    public int[] solution(int k, int[] score) {
        
        int[] result = new int[score.length];
        List<Integer> list = new ArrayList<>();
        
        for (int i = 0; i < score.length; i++) {
            list.add(score[i]);
            
            if (list.size() > k)
                list.remove(Collections.min(list));
            
            result[i] = Collections.min(list);
        }
        
        return result;
    }
}

진행 흐름은 비슷하다.

우선순위 큐를 선언하는 대신 List를 선언한 후 for문을 통해 핵심 코드가 진행된다.

 

먼저 list.add() 로 list에 현재 score 값을 삽입해준다.

이후 size 를 k와 비교하여, 만약 수용하는 범위인 k보다 해당 리스트의 크기가 더 크면 list.remove() 을 통해서 가장 작은 수를 삭제해준다. 이때, Collections에서 제공하는 Collections.min() 를 통해 최솟값을 골라 제거해주었다.

마지막으로 Collections.min() 을 사용하여, 현재 리스트에서 가장 작은 수를 result 배열에 저장해주었다.

 

 

두 방식의 차이점을 알아보기 위해 소요된 시간을 알아보았다.

 

위가 우선순위 큐를 사용한 방식이고,

아래가 리스트를 사용한 방식이다.

 

위에서 확인할 수 있듯이, 우선순위 큐를 사용한 방식이 훨씬 효율적이었다.

PriorityQueue는 최소 힙이다. score.length = n 이라고 가정하면, 한 번 반복할 때의 시간복잡도는 아래와 같다.

for (int i = 0; i < score.length; i++) {
    pq.add(score[i]);              // 시간복잡도: O(log k)
    if (pq.size() > k) pq.poll();  // 시간복잡도: O(log k)
    result[i] = pq.peek();         // 시간복잡도: O(1)
}

즉, 한 번 반복할 때의 시간 복잡도는

O(log k) + O(log k) + O(1) = O(log k)

이고, 전체 n번 반복하므로 O(n log k) 가 된다.

 

반면 리스트를 사용하는 방식에서, for문 한 번 반복할 때의 시간복잡도는 아래와 같다.

for (int i = 0; i < score.length; i++) {
    list.add(score[i]);                      // 시간복잡도: O(1)
    if (list.size() > k) 
    	list.remove(Collections.min(list));  // 시간복잡도: O(k)
    result[i] = Collections.min(list);       // 시간복잡도: O(k)
}

즉, 한 번 반복할 때의 시간 복잡도는

O(1) + O(k) + O(k) = O(k)

이고, 전체 n번 반복하므로 O(nk) 가 된다.

 

따라서 k 값이 커질수록 우선순위 큐를 사용한 풀이가 더 효율적인 성능을 보이게 된다.

 

 

---

 

 

ref.

🔗 https://blog.naver.com/guen5997/223145269088