[Lv.3] 야근 지수 [프로그래머스_코딩테스트] [Greedy]

🔍 문제 요약

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

프로그래머스

 

근무 시간인 Works가 int 배열로 주어지고 n이라는 근무 시간이 주어질 때 야근 시간은 works에서 근무시간을 뺀 후 남은 시간들을 제곱한 시간의 합으로 구한다고 한다. 야근이 최소시간이 될 때의 값을 구하면 된다.

 

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

제곱을 한 수의 합이 가장 작은 것은 어떻게 구하느냐로 접근해야 한다. 먼저 생각했던 방식은 사실 큰수를 최대한 줄이는 거가 맞지?라는 거는 생각을 했다. 그것을 풀이로 했을 때 생각한 것이 조금 잘못 되었는지 테스트 케이스가 실패가 우수수 나왔지만.. 필자가 생각했던 풀이는 값들을 최대한 평균값으로 맞추면 되지 않을까라는 방식이었다. (사실 어떻게 하면 결과적으로 최소값이 된다는 것인지 알지 못해서 적당하게 풀었던 느낌..) 아래의 코드가 필자가 접근한 방식

using System;

public class Solution
{
    /// <summary>
    /// 야근 지수
    /// https://school.programmers.co.kr/learn/courses/30/lessons/12927
    /// </summary>
    public long solution(int n, int[] works) {
        long answer = 0;
        
        // 핵심 : Works의 시간들에서 n만큼의 시간을 뺐을 때 남은 시간들의 제곱의 합이 최소가 되는 방법을 찾기
        // 생각해낸 방법은 일단 Works의 합산에서 n을 빼고 works의 개수로 나누어서 평균을 구한다. (소수가 나오면 내림)
        // 그렇게 나온 평균 값을 works에섯 순회하면서 각 근무시간을 평균시간까지 조절해서 n에서 뺴주기
        int sumWork = 0;
        int workCount = works.Length;
        
        // 가장 큰 숫자에서 내림차순으로 내려줌. 가장 큰 걸 없애는 걸 목표로 해야 제곱의 합산 값이 줄어들 것
        Array.Sort(works);
        Array.Reverse(works);

        foreach (var work in works)
        {
            sumWork += work;
        }

        if (sumWork <= 0) return 0;

        // 작업 남은 시간 평균 (나머지는 내림)
        int avgWork = sumWork / workCount;

        // works 배열에 평균 시간까지 순서대로 맞춰줌
        for (int i = 0; i < workCount; i++)
        {
            int diff = works[i] - avgWork;

            if (diff > 0)
            {
                if (n < diff)
                {
                    works[i] -= n;
                    n = 0;
                }
                else
                {
                    works[i] -= diff;
                    n -= diff;
                }
            }

            // 더 남은 근무 시간 없는 경우
            if (n <= 0) break;
        }

        // 남은 n은 work 개수에 맞게 되도록 균등하게 줄여줌
        if (n > 0)
        {
            int avgNamWork = n / workCount;
            int namAvgWork = n % workCount;

            for (int i = 0; i < works.Length; i++)
            {
                works[i] -= avgNamWork;

                // 균등하게 뺐을 때 남은 수치가 있는 경우 1씩 더 빼줌
                if (works[i] > 0 && namAvgWork > 0)
                {
                    works[i] -= 1;
                    namAvgWork -= 1;
                }
            }
        }
        
        // 결과 합산
        foreach (var work in works)
        {
            answer += work * work;
        }
        
        return answer;
    }
}

/// <summary>
/// C# 7.3
/// </summary>
internal class Program
{
    public static void Main(string[] args)
    {
        var sl = new Solution();
        var works1 = new int[] { 4, 3, 3 };
        int n1 = 5;
        var works2 = new int[] { 2, 1, 2 };
        int n2 = 1;
        var works3 = new int[] { 1, 1 };
        int n3 = 3;
        
        Console.WriteLine("r1:{0}, n1: {1}", sl.solution(n1, works1), n1);
        Console.WriteLine("r2:{0}, n2: {1}", sl.solution(n2, works2), n2);
        Console.WriteLine("r3:{0}, n3: {1}", sl.solution(n3, works3), n3);
    }
}

 

코드가 생각보다 길어졌는데, 사실 한 번은 풀어서 제출을 해봤다가 테스트 케이스가 너무 길어져서 좀 더 보완을 해본다보니 더 길어졌고 사실상 그것도 틀린 결과를 도출해 내었다. 결국 gpt에게 도움을 구했던 케이스.

 

✅ 풀이 코드

public class Solution {
    public long solution(int n, int[] works) {
        var workList = new List<int>(works);

        while (n > 0) {
            // 가장 큰 값 찾아서 1 줄이기
            workList.Sort(); // 내림차순 정렬 대체
            workList.Reverse();

            if (workList[0] == 0) break; // 더 줄일 게 없음

            workList[0] -= 1;
            n--;
        }

        long answer = 0;
        foreach (var w in workList) {
            answer += (long)w * w;
        }

        return answer;
    }
}

 

문제를 정말 간단하게 생각해서 가장 큰 값을 일단 줄인다로 접근하는 Greedy한 문제였다. C# 7.3을 기준으로 풀다 보니 우선순위 큐는 쓰지 못하였지만 gpt가 추천했던 방식은 우선순위큐. 

가장 큰 수를 줄여야 제곱의 합은 작은 값이 된다

 

일단 그래서 문제의 풀이 자체는 매우 간략하다. 말그대로 반복을 돌면서 제일 큰 숫자부터 1을 줄이고 근무시간 n 1줄이고, 다음으로 제일 큰 숫자 1 줄이고 n 1줄이고 ... 을 하는 것이 전부이다. 

 

🔄 정리

문제의 핵심을 먼저 제대로 파악하고 문제를 풀면 정말 빠르게 풀 수 있지 않았을까 싶은 문제였다. Greedy 문제이기에 어떻게 보면 그게 당연할 수 있긴 하다. 아무튼 제곱합은 가장 큰 숫자를 줄이는게 핵심이다는 것을 꼭 기억하기로...