[Lv.1] 체육복 [프로그래머스_코딩테스트] [Greedy]

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

프로그래머스

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
    /// <summary>
    /// 체육복
    /// https://school.programmers.co.kr/learn/courses/30/lessons/42862
    /// </summary>
    public int solution(int n, int[] lost, int[] reserve)
    {
        var lostSet = new HashSet<int>(lost);
        var reserveSet = new HashSet<int>(reserve);

        var intersection = new HashSet<int>(lostSet);
        intersection.IntersectWith(reserveSet);

        // 중복 제거
        lostSet.ExceptWith(intersection);
        reserveSet.ExceptWith(intersection);
        
        var reserveQueue = new Queue<int>(reserveSet.OrderBy(x => x));
        var lostQueue = new Queue<int>(lostSet.OrderBy(x => x));

        int count = 0;

        for (int i = 1; i <= n; i++)
        {
            if (lostQueue.Count == 0)
            {
                count++;
                continue;
            }
            
            int lPeek = lostQueue.Peek();

            // 잃어버리지 않은 경우
            if (lPeek != i)
            {
                count++;
                continue;
            }
            
            if (reserveQueue.Count == 0)
            {
                continue;
            }
            
            int rPeek = reserveQueue.Peek();
            
            // 잃어버린 번호에서 1의 차이가 나는 경우 reserve에서 뺌
            
            if (lPeek > rPeek)
            {
                if (lPeek - rPeek == 1)
                {
                    count++;
                }
                
                lostQueue.Dequeue();
                reserveQueue.Dequeue();
            }
            else if (rPeek > lPeek)
            {
                if (rPeek - lPeek == 1)
                {
                    reserveQueue.Dequeue();
                    count++;
                }
                
                lostQueue.Dequeue();
            }
        }
        
        return count;
    }
}

/// <summary>
/// C# 7.3
/// </summary>
internal class Program
{
    public static void Main(string[] args)
    {
        var sl = new Solution();
        int n = 3;
        int[] lost = { 2, 3 };
        int[] reserve = { 3 };
        Console.WriteLine(sl.solution(n, lost, reserve));
    }
}

 

위의 풀이 코드는 실패 테스트 케이스가 존재하는 코드다. for를 모든 번호대로 돌면서 체크를 하면 문제가 되는 케이스가 발생하지 않게 될 것이라고 생각을 했었는데 어디선가 문제가 생기는 것으로 보인다.

 

그래서 길다란 for문을 정리하는 방향으로 gpt에게 피드백을 받은 코드

 

public int solution(int n, int[] lost, int[] reserve)
    {
        var lostSet = new HashSet<int>(lost);
        var reserveSet = new HashSet<int>(reserve);

        var intersection = new HashSet<int>(lostSet);
        intersection.IntersectWith(reserveSet);

        // 중복 제거
        lostSet.ExceptWith(intersection);
        reserveSet.ExceptWith(intersection);
        
        var reserveQueue = new Queue<int>(reserveSet.OrderBy(x => x));
        var lostQueue = new Queue<int>(lostSet.OrderBy(x => x));

        int count = n - lostQueue.Count;

        while (lostQueue.Count > 0 && reserveQueue.Count > 0)
        {
            int l = lostQueue.Peek();
            int r = reserveQueue.Peek();

            if (Math.Abs(l - r) == 1)
            {
                // 앞뒤 번호일 경우 빌려주기 성공
                lostQueue.Dequeue();
                reserveQueue.Dequeue();
                count++;
            }
            else if (l < r)
            {
                // 잃어버린 학생이 더 앞 번호면 빌릴 수 없으므로 그냥 제거
                lostQueue.Dequeue();
            }
            else
            {
                // 여벌 학생이 더 앞 번호면 빌려줄 수 없음
                reserveQueue.Dequeue();
            }
        }
        
        return count;
    }

 

일단 해당 방식은 두개의 큐를 모두 돌면서 체육복을 빌려줄 수 있는 경우에만 count를 늘리고 lost큐와 reserve큐를 비워나가는 형태로 짜주었다. 일단 이것보다 더 간단한 형태는 아래와 같은 형태이므로 참고..

 

public int solution(int n, int[] lost, int[] reserve)
{
    var lostList = lost.ToList();
    var reserveList = reserve.ToList();
    var intersect = lostList.Intersect(reserveList).ToList();

    lostList = lostList.Except(intersect).OrderBy(x => x).ToList();
    reserveList = reserveList.Except(intersect).OrderBy(x => x).ToList();

    foreach (var r in reserveList)
    {
        if (lostList.Contains(r - 1))
            lostList.Remove(r - 1);
        else if (lostList.Contains(r + 1))
            lostList.Remove(r + 1);
    }

    return n - lostList.Count;
}

 

어떻게 보면 핵심은 학생 수 - 체육복 없는 학생수 인데 이걸 풀기 위해 Queue라는 자료구조에 너무 집착하게 풀려고 했던 것 같다.

추가로 알고리즘을 짤 때 하나하나 예외처리 하는 방식이 아니라 로직적으로 깔끔한 형태로 개선을 위해 공부가 필요할 듯 해보인다.

 

추가로 교집합을 구하는 부분에서 GC를 유발하지 않기 위해서 HastSet<T>.IntersectWith()를 하는 방향이 낫다.