[Lv.1] 명예의 전당(1) [프로그래머스_코딩테스트] [정렬, min-heap]

🔍 문제 요약

https://school.programmers.co.kr/learn/courses/30/lessons/138477

프로그래머스

명예의 전당이라는 점수 줄 세우는 문제로 k개의 점수만 높은 순서대로 뽑아서 그 중에서 가장 낮은 점수를 일차별로 배열에 저장해서 도출해내는 문제.

 

🧠 나의 접근 방식과 시행착오

해당 문제는 일단 생각나는 대로 빠르게 코딩을 하였고, 실패 케이스 없이 정상 동작하였다. 다만 최적화면에서 Sort를 너무 자주 돌려야 하는 부분이 있어서 이 문제는 개선의 여지가 있다고 봄. gpt가 문제를 추천했을 때에도 분류가 우선순위 큐였기에.. 일단 아래처럼 간단히 문제를 푼 것을 공유 해두고 풀이 쪽에서 제대로 우선순위 큐로 변경해보자.

using System;
using System.Collections.Generic;

public class Solution
{
    /// <summary>
    /// 명예의 전당 (1)
    /// https://school.programmers.co.kr/learn/courses/30/lessons/138477
    /// </summary>
    public int[] solution(int k, int[] score)
    {
        int[] answer = new int[score.Length];
        
        // 점수 리스트를 넣고 정렬을 돌리는 방향으로 고민.
        var scoreList = new List<int>();

        for (int day = 1; day <= score.Length; day++)
        {
            scoreList.Add(score[day - 1]);
            scoreList.Sort((x, y) => x.CompareTo(y));

            answer[day - 1] = scoreList[scoreList.Count - 1 - (Math.Min(k, day) - 1)];
        }
        
        return answer;
    }
}

/// <summary>
/// C# 7.3
/// </summary>
internal class Program
{
    public static void Main(string[] args)
    {
        var sl = new Solution();
        int k1 = 3;
        var scoreArr1 = new [] {10, 100, 20, 150, 1, 100, 200};
        int k2 = 4;
        var scoreArr2 = new [] {0, 300, 40, 300, 20, 70, 150, 50, 500, 1000};
        var res1 = sl.solution(k1, scoreArr1);
        var res2 = sl.solution(k2, scoreArr2);
    }
}

✅ 풀이 코드

지금 다시 보니 PriorityQueue의 경우 C# 10 이상 버젼에서 사용 가능한 형태라 프로그래머스가 7.3까지만 지원을 하고 있어서 이 부분은 불가능한 점을 알게됨. 그래서 이 문제는 Sort에서 모든 점수를 다 정렬하지 않고 min-heap을 써서 최소한으로 정렬을 하는 방법에 대해서 코드 개선을 해보는 것으로 결정.

public class Solution {
    public int[] solution(int k, int[] score) {
        var answer = new int[score.Length];
        var minHeap = new List<int>();

        for (int i = 0; i < score.Length; i++) {
            minHeap.Add(score[i]);
            minHeap.Sort(); // min-heap 대체 (간단화용)

            if (minHeap.Count > k)
                minHeap.RemoveAt(0); // 가장 낮은 점수 제거

            answer[i] = minHeap[0]; // 현재 명예의 전당 최소 점수
        }

        return answer;
    }
}

 

🔄 정리

문제를 보면 Sort가 시간이 오래 걸릴 수 있는 부분을 해결한 것. 단순하고 이해에도 어렵지 않게 되어 있어서 괜찮은 듯 하다. 간단하게 점수를 k개보다 더 많이 쌓이게 되면 가장 작은 것을 지워서 높은 점수들만 남겨두는 형태이다. 물론 C# 7.3까지만 지원되는 프로그래머스에 기준에서 작업된 코드라서 실제로 추천하는 방향은 SortedSet이나 PriorityQueue<TElement, TPriority> (C# 10 이상) 사용 가능하면 훨씬 깔끔하게 처리된다고 한다. (위 와 같이 돌리게 되어도 O(logN)으로 동작하고 있ㅇ므)