명예의 전당에는 최대 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의 순서를 뒤집어준다.
'Java > Coding Test' 카테고리의 다른 글
| 과일 장수 문제 풀이 (0) | 2023.09.28 |
|---|---|
| 2016년 문제 풀이 (0) | 2023.09.28 |
| 가장 가까운 같은 글자 문제풀이 (0) | 2023.09.26 |
| 시저 암호 문제풀이 (0) | 2023.09.25 |
| 삼총사 문제풀이 (0) | 2023.09.25 |