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

제가 짠 코드는 항상 시간 복잡도가 엉망인 모양이네요.. 알고리즘에 필요한 것들을 공부해야겠습니다. ㅠ

 

먼저 제가 짠 코드입니다.

 

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

		List<Integer> arrList = new ArrayList<>();
		List<Integer> ansList = new ArrayList<>();

		for (int i = 0; i < k; i++) {
			arrList.add(score[i]);
			Collections.sort(arrList);
			ansList.add(arrList.get(0));
		}

		for (int i = k; i < score.length; i++) {
			if (score[i] > arrList.get(0)) {
				arrList.remove(0);
				arrList.add(score[i]);
				Collections.sort(arrList);
			}
			ansList.add(arrList.get(0));
		}

		int[] answer = new int[ansList.size()];

		for (int i = 0; i < ansList.size(); i++) {
			answer[i] = ansList.get(i);
		}

		return answer;
	}

 

기능 구현에만 초점이 맞춰져 있고, 정렬을 많이 사용하다보니 채점  테스트에서 시간이 초과해버리더군요.. 해결법이 떠오르지 않아 검색을 통해 해결법을 찾았습니다.

 

import java.util.PriorityQueue;

public int[] solution(int k, int[] score) {
    // 우선순위 큐를 사용하여 항상 최소값을 관리
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    int[] answer = new int[score.length];
    
    for (int i = 0; i < score.length; i++) {
        // 점수를 추가
        if (i < k) {
            minHeap.add(score[i]);
            answer[i] = minHeap.peek(); // k개 미만일 때는 현재 최소값
        } else {
            if (score[i] > minHeap.peek()) {
                minHeap.poll(); // 현재 최소값 제거
                minHeap.add(score[i]); // 새로운 점수를 추가
            }
            answer[i] = minHeap.peek(); // 현재 최소값
        }
    }

    return answer;
}

 

바로 PriorityQueue를 활용하는건데요, 일반적인 큐는 먼저 들어간 데이터가 먼저 나가는 구조인 FIFO 형식의 자료구조입니다. 반면에 우선순위 큐의 경우 들어가는 순서와는 상관없이 우선순위가 높은 데이터가 먼저 나가는 자료구조입니다. 즉, 값이 작은 숫자가 먼저 나가게 되는 것이죠!

 

이렇게 하면 정렬을 굳이 하지 않아도 우선순위가 낮은(숫자가 낮은) 값이 계속해서 먼저 나올 수 있기 때문에 시간복잡도에서 이점을 챙길 수 있는거죠!

 

좋은 방법을 알았네요. 다음에 써봐야겠습니다.