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

프로그래머스 - 명예의 전당 (1)

풀이

1. ArrayList에 점수를 추가
2. ArrayList의 개수가 k개가 넘어가면 가장 작은 요소를 삭제
3. ArrayList에서 가장 작은 요소를 반환할 배열 result에 저장

코드

import java.util.*;

public class HallOfFame {
	public int[] solution(int k, int[] score) {
		int[] result = new int[score.length];
		ArrayList<Integer> rank = new ArrayList<>();

		for (int i = 0; i < score.length; i++) {
			rank.add(score[i]);
			if (i >= k) rank.remove(Collections.min(rank));
			result[i] = Collections.min(rank);
		}
		return result;
	}

	public static void main(String[] args) {
		HallOfFame hallOfFame = new HallOfFame();

		String output1 = Arrays.toString(hallOfFame.solution(3, new int[]{10, 100, 20, 150, 1, 100, 200}));
		System.out.println(output1.equals("[10, 10, 10, 20, 20, 100, 100]"));
		String output2 = Arrays.toString(hallOfFame.solution(4, new int[]{0, 300, 40, 300, 20, 70, 150, 50, 500, 1000}));
		System.out.println(output2.equals("[0, 0, 0, 0, 20, 40, 70, 70, 150, 300]"));
		String output3 = Arrays.toString(hallOfFame.solution(5, new int[]{2, 3, 1}));
		System.out.println(output3.equals("[2, 2, 1]"));
	}
}

PriorityQueue 우선순위 큐

데이터에 우선순위가 있는 큐

이진트리 힙으로 구성

import java.util.PriorityQueue;

//낮은 숫자가 우선 순위(default)
PriorityQueue<Integer> priorityQueueLowest = new PriorityQueue<>();

//높은 숫자가 우선 순위
PriorityQueue<Integer> priorityQueueHighest = new PriorityQueue<>(Collections.reverseOrder());

❗️priority queue로 작성한 solution

public int[] solution(int k, int[] score) {
	int[] result = new int[score.length];
    PriorityQueue<Integer> rank = new PriorityQueue<>();
    
    for (int i = 0; i < score.length; i++) {
    	rank.add(score[i]);
    	if (i >= k) rank.poll();
        result[i] = rank.peek();
    }
    return result;
}