[프로그래머스 | C#] 명예의 전당 (1) List.Sort, heap 삽입-제거 구현

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

프로그래머스

코드

매 주마다 점수를 받고, 그 주 마다 k 번째 순위 안에 드는 점수 중 가장 낮은 점수를 answer 배열에 넣어 반환한다.

매 주마다 받은 모든 점수는 score 배열에 들어있다.

using System;
using System.Collections.Generic;

namespace ConsoleApplication1
{
    public class 명예의_전당__1_
    {
        // static void Main()
        // {
        //     var answer = solution(3, new [] { 10, 100, 20, 150, 1, 100, 200 });
        //     foreach (var a in answer)
        //     {
        //         Console.Write(a + " ");
        //     }
        // }

        public static int[] solution(int k, int[] score) 
        {
            int[] answer = new int[score.Length];
            List<int> rank = new List<int>();
            for (int i = 0; i < score.Length; i++)
            {
            	// 1)
                if (rank.Count < k)
                {
                    rank.Add(score[i]);
                }
                // 2)
                else
                {
                    if (rank[0] < score[i])
                    {
                        rank[0] = score[i];
                    }
                }
                // 3)
                rank.Sort();
                answer[i] = rank[0];
            }
            return answer;
        }
    }
}

1) k명의 사람이 채워지기 전에는 모든 사람이 k개의 순위권에 든다. 따라서 순위 리스트 rank를 변경하지 않고 값을 Add만 한다.

2) k명이 다 채워졌다면, 순위 리스트를 변경해야한다. 또한 매 주마다 새로운 점수가 들어오기 때문에 새로 들어온 값 score[i]가 현재 순위권 안에 있는 점수보다 크다면 순위 리스트를 변경해야한다.

3) 변경된 순위 리스트를 오름차순으로 정렬한다. 정렬한 후에는 0번째에 있는 값이 가장 낮은 값이 되므로 rank[0]을 answer 배열에 넣는다.

 

List.Sort

List를 정렬하는 메서드이다.

기본형은 아래와 같으며, 매개변수 comparision은 비교 조건이다.

비교 조건을 넣지 않으면 해결 코드와 같이 오름차순으로 정렬된다.

public void Sort (Comparison<T> comparison);

아래와 같이 비교 조건을 넣어 내림차순으로 만들 수도 있다.

다른 상세한 조건을 넣으려면 비교 클래스를 만들어 매개변수로 넣어 쓸 수도 있다.

using System;
using System.Collections.Generic;

namespace ConsoleApplication1
{
    internal class Program
    {
        static void Main()
        {
            List<int> list = new List<int> { 5, 3, 1, 4, 2 };
            list.Sort(new Comparison<int>((n1, n2) => n2.CompareTo(n1)));
            foreach (var val in list)
            {
                Console.Write($"{val}, ");
            }
            // 출력: 5, 4, 3, 2, 1,
        }
    }
}

https://learn.microsoft.com/ko-kr/dotnet/api/system.collections.generic.list-1.sort?view=net-7.0 

List<T>.Sort 메서드 (System.Collections.Generic)

heap 삽입(HInsert), 제거(HDelete)

heap(힙)은 완전 이진 트리로, 모든 노드에 저장된 값이 자식 노드에 저장된 값보다 크거나 같아야 하는 조건을 가진다. 즉, 루트 노드의 값이 가장 커야한다.

힙은 min heap, max  heap 이 있는데, max heap은 루트 노드의 값이 가장 큰 조건일 때의 heap이고, min heap은 루트 노드의 값이 가장 작을 때의 heap이다.

 

문제에 적용해보면 힙에 들어갈 수 있는 점수 수를 k로 제한하고 힙에 점수가 들어갈 때마다 가장 작은 값이 루트에 놓이게 하여 결론적으로 루트 값을 answer 배열에 넣으면 문제를 풀 수 있다.

 

아래의 코드에서는 min heap의 삽입, 제거를 보인다.

void HInsert(ref List<int> buf, int item)
{
    buf.Add(item);
    int index = buf.Count - 1;
    while (index > 0)
    {
        int parent = (index - 1) / 2;
        if (buf[parent] > buf[index])
        {
            int tmp = buf[parent];
            buf[parent] = buf[index];
            buf[index] = tmp;
            index = parent;
        }
        else break;
    }
}

void HDelete(ref List<int> buf)
{
    int root = buf[0];
    buf[0] = buf[buf.Count - 1];
    buf.RemoveAt(buf.Count - 1);

    int index = 0;
    int last = buf.Count - 1;
    while (index < last)
    {
        int child = index * 2 + 1;
        if (child < last && buf[child] > buf[child + 1])
            child = child + 1;
        if (child > last || buf[index] <= buf[child])
            break;
                    
        int tmp = buf[child];
        buf[child] = buf[index];
        buf[index] = tmp;
        index = child;                                    
    }
}

- 삽입

삽입된 원소는 트리의 가장 마지막에 포함된다. 들어온 원소가 부모 노드의 값보다 작으면 들어온 값과 부모 값을 swap한다. 그 값을 계속 위로 비교-swap한다. 만약 들어온 값이 루트 값 보다 작다면 루트 노드까지 swap이 이루어지며 결론적으로 루트 노드의 값이 바뀌게 된다.

- 삭제

루트 노드의 값을 제거한다. 그 후 트리의 가장 마지막 값을 루트에 넣고 루트에 넣은 값을 자식 노드의 값과 비교하며 자식 노드와 현재 노드를 swap한다. 만약 루트에 들어간 값이 가장 큰 값이라면 루트의 마지막 위치에 놓일 때까지 계속 자식 노드와 비교하며 swap한다.

 

문제에 적용한다면 아래와 같이 사용할 수 있다.

public static int[] solution(int k, int[] score) 
{
    int[] answer = new int[score.Length];
    List<int> buffer = new List<int>();
    for (int i = 0; i < score.Length; i++)
    {
        HInsert(ref buffer, score[i]);
        if (buffer.Count > k)
            HDelete(ref buffer);
        answer[i] = buffer[0];
    }
    return answer;
}