명예의 전당(1) 문제풀이

명예의 전당에는 최대 n개의 수가 들어갈 수 있으며, n개 이후부터 추가될 때에는 

명예의 전당에 있는 수보다 큰 수가 들어오면 가장 작은 수는 빠진다. 

명예의 전당에 수가 추가될 때마다 명예의 전당에 있는 수 중 가장 작은 수를 배열로 반환 

 

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

int[] answer = new int[score.length];

ArrayList<Integer> honors = new ArrayList<Integer>();

for (int i = 0; i < score.length; i++) {

if (i < k) {

honors.add(score[i]);

Collections.sort(honors);

} else if (score[i] >= honors.get(0)) {

honors.add(score[i]);

Collections.sort(honors);

honors.remove(0);

}

answer[i] = honors.get(0);

}

return answer;

}

리스트에 수를 넣는데 매번 가장 작은 수를 찾아서 제거한다. 

가장 작은 수를 찾기 위해 매 반복마다 정렬을 수행하는데 

대신 priority Queue 를 사용하면 가장 작은 수를 찾아서 poll 할 수 있다. 

public int[] solution2(int k, int[] score) {

int[] answer = new int[score.length];

 

PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

for (int i = 0; i < score.length; i++) {

priorityQueue.add(score[i]);

if (priorityQueue.size() > k) {

priorityQueue.poll();

}

answer[i] = priorityQueue.peek();

}

return answer;

}

k일 이전까지는 계속 추가하고 가장 앞의 값을 answer 배열에 추가하고 

k일 이후부터는 원소 추가 이후 가장 작은 값을 없애고 answer 배열에 남은 수 중 가장 작은 값을 추가한다.

 

priorityQueue는 가장 작은 수를 우선순위로 둔다. 

만약 가장 큰 수를 우선순위로 두고 싶다면 

PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

Collections.reverseOrder()로 queue의 순서를 뒤집어준다.