[Lv.2] 귤 고르기 [프로그래머스_코딩테스트] [Greedy, 정렬] [30분]

🔍 문제 요약

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

프로그래머스

수확한 귤 사이즈 별로 배열 (tangerine)이 주어질 때 귤 k개를 골라서 크기가 서로 같은 것을 최대로 해서 값을 구하는 문제

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

풀이에 약 40분 정도 소요. 더 나은 자료구조를 생각해보려고 했다가 잘 쓰지 않던 SortedList 같은 것도 고민했으나 IComparer를 직접 구현해야 하는 부분이 있어서 시간 소요만 함.. 일단 Count를 size별로 체크한 뒤에 더 많은 개수부터 해서 내림차순으로 정렬시키면 된다고 생각을 하여 Dictionary에 한 번 넣고 List에 (size, count)대로 넣고 정렬을 시켰다. 그 후 k개에서 하나씩 빼면서 체크하는 방식으로 문제를 해결. 푼 방식은 아래와 같다.

using System;
using System.Collections.Generic;

public class Solution
{
    /// <summary>
    /// 귤 고르기
    /// https://school.programmers.co.kr/learn/courses/30/lessons/138476
    /// </summary>
    public int solution(int k, int[] tangerine)
    {
        // index가 size로 보고 해당 하는 value는 갯수
        Dictionary<int, int> countDict = new Dictionary<int, int>();

        foreach (var item in tangerine)
        {
            if (countDict.ContainsKey(item))
            {
                countDict[item]++;
            }
            else
            {
                countDict.Add(item, 1);
            }
        }
        
        List<(int, int)> list = new List<(int, int)>();

        foreach (var item in countDict)
        {
            list.Add((item.Key, item.Value));
        }
        
        // 개수별로 내림차순 정렬
        list.Sort((a, b) => b.Item2 - a.Item2);
        
        int answer = 0;

        foreach (var item in list)
        {
            if (k == 0) break;
            
            if (k >= item.Item2)
            {
                k -= item.Item2;
                answer++;
            }
            else
            {
                answer++;
                break;
            }
        }

        return answer;
    }
}

/// <summary>
/// C# 7.3
/// </summary>
internal class Program
{
    public static void Main(string[] args)
    {
        var sl = new Solution();
        var tangerine1 = new int[] { 1, 3, 2, 5, 4, 5, 2, 3 };
        int k1 = 6;
        var tangerine2 = new int[] { 1, 3, 2, 5, 4, 5, 2, 3 };
        int k2 = 4;
        var tangerine3 = new int[] { 1, 1, 1, 1, 2, 2, 2, 3 };
        int k3 = 2;

        Console.WriteLine(sl.solution(k1, tangerine1));
        Console.WriteLine(sl.solution(k2, tangerine2));
        Console.WriteLine(sl.solution(k3, tangerine3));
    }
}

 

✅ 풀이 코드

피드백을 받은 부분에서 개선 가능한 부분은 List<(int, int)>를 쓰지 않고 List<int>로 개수만 쭉 넣어도 된다. 풀고 나서 생각해보니 size는 의미가 없음.. 추가로 변수명도 list에서 countList와 같이 의미가 확실한 것으로 교체가 나을 것. 또, Linq를 써서 간략하게 코드를 짜게 된다면 아래와 같이 개선도 가능하다. 

var sortedCounts = countDict.Values.OrderByDescending(v => v).ToList();

되도록 Linq는 안 쓰려고 하다 보니 굳이 저렇게 사용하기 보다는 아래처럼 하는 것이 더 나아보인다.

추가로 어떻게든 gc를 줄이기 위해서 Span<T>나 ArrayPool 기반 직접 정렬도 고려할 수는 있다고 한다.

🔄 정리

생각외로 처음 문제를 풀 때 다른 자료구조를 복잡하게 접근하면서 시간을 허비한 문제. Dictionary에 넣고 List에 넣고 정렬하는 형태로 결국 풀이는 된다. Dict 하나에서 어떻게 처리가 될 수 있으면 좋을텐데 그런 좋은 방법은 없겠지..