명예의 전당 (1)

작성일: 2024-11-02

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/138477

접근 방식

점수를 리스트에 넣고 내림차순 정렬을 한다.

반복문을 돌리면서, i가 k-1보다 작은경우에는 i번째 인덱스를 answer에 저장하고

큰 경우에는, list에서 k-1번째 인덱스를 answer에 저장한다.

결과

소스 코드

import java.util.*;

class Solution {
    public int[] solution(int k, int[] score) {
        int[] answer = new int[score.length];
        List<Integer> list = new ArrayList<>();
        int tmp = -1;
        for(int i=0; i<score.length; i++){
            list.add(score[i]);
            Collections.sort(list, Collections.reverseOrder());
            if(i<k-1){
                answer[i] = list.get(i);
            } else{
                answer[i] = list.get(k-1);
            }
        }


        return answer;
    }
}

다른 접근 방식

우선순위큐를 이용한 문제 풀이가 있었다.

나도 사실 맨 처음에는 우선순위큐를 이용한 문제풀이를 생각했었지만 어떻게 이용해야 할지 감이 안 잡혀서, 이용하지 못했다.

내림차순이라는 것에 너무 집작하다보니, 큐는 FIFO이기에 맨 뒤 객체에 접근할 수 없어서 풀 수 없다고 판단했다.

하지만, 오름차순으로 접근해서 큐 사이즈를 3개로 관리했다면 풀 수 있었을 것이다.

import java.util.*;

class Solution {
    public int[] solution(int k, int[] score) {
        int[] answer = new int[score.length];
        PriorityQueue<Integer> q = new PriorityQueue<>();
        int tmp = -1;
        for(int i=0; i<score.length; i++){
            q.offer(score[i]);
            if(i<k){
                answer[i] = q.peek();
            } else{
                q.poll();
                answer[i] = q.peek();
            }
        }
        return answer;
    }
}

알게 된 점

문제를 바라보는 시각을 좀 더 넓혀서, 역으로 풀 수 있는 방법에 대해서 생각해보는 계기가 되었다.