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

 

코딩테스트 연습 - 명예의 전당 (1) | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

문제설명

"명예의 전당"이라는 TV 프로그램에서는 매일 1명의 가수가 노래를 부르고, 시청자들의 문자 투표수로 가수에게 점수를 부여합니다. 매일 출연한 가수의 점수가 지금까지 출연 가수들의 점수 중 상위 k번째 이내이면 해당 가수의 점수를 명예의 전당이라는 목록에 올려 기념합니다. 즉 프로그램 시작 이후 초기에 k일까지는 모든 출연 가수의 점수가 명예의 전당에 오르게 됩니다. k일 다음부터는 출연 가수의 점수가 기존의 명예의 전당 목록의 k번째 순위의 가수 점수보다 더 높으면, 출연 가수의 점수가 명예의 전당에 오르게 되고 기존의 k번째 순위의 점수는 명예의 전당에서 내려오게 됩니다.

 

이 프로그램에서는 매일 "명예의 전당"의 최하위 점수를 발표합니다. 예를 들어, k = 3이고, 7일 동안 진행된 가수의 점수가 [10, 100, 20, 150, 1, 100, 200]이라면, 명예의 전당에서 발표된 점수는 아래의 그림과 같이 [10, 10, 10, 20, 20, 100, 100]입니다.

[ 예시 ]

명예의 전당 목록의 점수의 개수 k, 1일부터 마지막 날까지 출연한 가수들의 점수인 score가 주어졌을 때, 매일 발표된 명예의 전당의 최하위 점수를 return하는 solution 함수를 완성해주세요.

제한사항

• 3 ≤ k ≤ 100
• 7 ≤ score의 길이 ≤ 1,000
  • 0 ≤ score[i] ≤ 2,000

접근 방법

우선, 해당 문제에서 내가 주의깊게 본 문장은 2개였다.

1. 출연 가수의 점수가 명예의 전당에 오르게 되고 기존의 k번째 순위의 점수는 명예의 전당에서 내려오게 됩니다
2. 매일 "명예의 전당"의 최하위 점수를 발표합니다.

이 2개를 통해, 삽입 & 최소값 삭제가 빈번한 상황에도 성능이 보장돼야 하며,
정렬 또한 이뤄져야 하는 컨테이너를 고민하던 중, 우선순위 큐 ( Priority Queue )가 떠올랐다. 

 

문제가 최저 점수를 제거하는 것이 아닌, 평균에서 가까운 가수를 제거하는 것이었으면

더 고민을 해야겠지만, 최저 점수를 제거하는 것이다보니 현재 상황에서는 우선순위 큐만한 것이 없었다.

 

구현은 이렇게 했다.

1. 랭킹에 점수를 넣는다.
2. 랭킹의 크기가 k를 넘어간다면, 최저 점수를 poll한다.
3. answer에 삽입한다.

1차 코드

import java.util.PriorityQueue;
import java.util.Queue;

class Solution {
    public int[] solution(int k, int[] score) {
        int[] answer = new int[score.length];
        Queue<Integer> ranking = new PriorityQueue<>();

        for(int s : score)
        {
            ranking.add(s);
            if(ranking.size() > k)
            {
                ranking.poll();
            }

            answer[day++] = ranking.peek();
        }

        return answer;
    }
}

 

코드 자체에는 문제가 없었으나, 이번과 같은 상황에서는 iterator를 사용한 for이 아닌 일반적인 for문을 사용하는 것이

조금의 성능이라도 더 올릴 수 있지 않았을까 생각이 들었다.

 

iterator를 사용한 for문이 아닌 일반 for문을 사용함에 있어 생기는 장점은 다음과 같았다

• 현재는 일자를 기록하는 day 변수를 선언했고, 증가 연산자를 통해 매일 1씩 늘려줬지만,
  일반 for문을 사용하게 될 경우 해당 과정은 제거할 수 있다.
• ranking.size()를 호출하지 않아도 for문에 사용된 변수가 k를 넘어가는 순간부터 if문을 사용하면 되기에,
  불필요한 함수 호출을 줄일 수 있다.

해당 함수로 변경하여 다시 구현하였고, 코드는 다음과 같다.

최종 코드

import java.util.PriorityQueue;
import java.util.Queue;

class Solution {
    public int[] solution(int k, int[] score) {
        int[] answer = new int[score.length];
        Queue<Integer> ranking = new PriorityQueue<>();

        for(int day = 0; day < score.length; ++day)
        {
            ranking.add(score[day]);
            if(day >= k)
            {
                ranking.poll();
            }

            answer[day] = ranking.peek();
        }

        return answer;
    }
}

 

해당 코드로 작성하였고 두 개의 속도를 비교해 봤을 때, k와 score가 작아서 그런지 유의미한 결과를 얻지는 못했다.

[ 좌 : 1차코드, 우 : 2차코드 ]

[ 통과 ]