[Lv.1] 최소직사각형 [프로그래머스_코딩테스트] [완전탐색, 정렬] [25분]

🔍 문제 요약

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

프로그래머스

가로 세로 길이가 들어있는 Sizes라는 배열이 주어지고 해당 사이즈들을 모두 포함할 수 있는 최소의 사이즈의 너비를 구하는 문제. (가로 세로 전환 가능)

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

대락 30분 정도 잡은 듯 하다. 문제에서 가로 세로를 전환할 수 있고 최소의 너비를 구하는 문제라 가로 최대, 세로 최대를 캐시하고 비교를 하면서 가로 세로를 전환했을 때에 포함이 되는 경우 캐시를 바꾸지 않고 넘어가고, 하나라로 넘치는 경우 전환했을 때와 전환하지 않았을 때 들어갈 수 있는 너비 중 더 작은 값으로 해서 계산하는 방식을 써봤다. 다만 이건 확신이 있게 푼 문제는 아니긴 함. 그렇지만 모든 테스트 케이스 통과한 문제긴 하다.

using System;

public class Solution
{
    /// <summary>
    /// 최소 직사각형
    /// https://school.programmers.co.kr/learn/courses/30/lessons/86491
    /// </summary>
    public int solution(int[,] sizes)
    {
        // 가로, 세로 최대 길이 비교용
        int rMax = 0;
        int hMax = 0;

        for (int i = 0; i < sizes.GetLength(0); i++)
        {
            int r = sizes[i, 0];
            int h = sizes[i, 1];

            // 1. 가로, 세로 둘 다 이전보다 작거나 같은 경우 상관 없이 다음 걸로 넘김
            if (r <= rMax && h <= hMax)
            {
                continue;
            }
            
            // 2. 가로, 세로 둘 중 하나라도 이전보다 큰 경우 90도로 꺾어봄 (r,h 반전)
            int rTemp = h;
            int hTemp = r;

            // 반전된 거가 이전거에 들어가는 경우 그냥 넘김
            if (rTemp <= rMax && hTemp <= hMax)
            {
                continue;
            }

            int resR1 = Math.Max(r, rMax);
            int resH1 = Math.Max(h, hMax);

            int resR2 = Math.Max(rTemp, rMax);
            int resH2 = Math.Max(hTemp, hMax);

            int current1 = resR1 * resH1;
            int current2 = resR2 * resH2;

            if (current1 < current2)
            {
                rMax = resR1;
                hMax = resH1;
            }
            else
            {
                rMax = resR2;
                hMax = resH2;
            }
        }
        
        int answer = rMax * hMax;
        return answer;
    }
}

/// <summary>
/// C# 7.3
/// </summary>
internal class Program
{
    public static void Main(string[] args)
    {
        var sl = new Solution();
        var size1 = new [,] { { 60, 50 }, { 30, 70 }, { 60, 30 }, { 80, 40 } };
        var size2 = new [,] { { 10, 7 }, { 12, 3 }, { 8, 15 }, { 14, 7 }, {5, 15} };
        var size3 = new [,] { { 14, 4 }, { 19, 6 }, { 6, 16 }, { 18, 7 }, { 7, 11} };
        
        Console.WriteLine(sl.solution(size1));
        Console.WriteLine(sl.solution(size2));
        Console.WriteLine(sl.solution(size3));
    }
}

✅ 풀이 코드

풀이의 핵심은 한쪽을 큰 값, 한 쪽은 작은 값으로 정렬하는 방식이다. 그렇게 하면 풀이 자체가 단순해진다. 한쪽으로 큰 값을 몰았기 때문에 뒤집어서 비교에 대한 풀이가 쉬워진다. 필자가 처음에 생각했던 것은 모든 경우를 다 비교해본다의 단순하게 생각했던 방식이라 풀이의 방식과 비교해보면 차이가 크게 보인다.

public int solution(int[,] sizes)
{
    int maxWidth = 0;
    int maxHeight = 0;

    for (int i = 0; i < sizes.GetLength(0); i++)
    {
        int w = sizes[i, 0];
        int h = sizes[i, 1];

        // 가로/세로를 큰 값이 앞으로 오도록 정렬
        int bigger = Math.Max(w, h);
        int smaller = Math.Min(w, h);

        // 전체 최대 가로/세로 갱신
        maxWidth = Math.Max(maxWidth, bigger);
        maxHeight = Math.Max(maxHeight, smaller);
    }

    return maxWidth * maxHeight;
}

🔄 정리

해당 문제처럼 모든 너비를 포함시킬 수 있는 최소값을 구하는 문제라면 한 쪽을 큰 값으로 고정한다라는 아이디어가 핵심일듯 하다. 일단 풀고 보는 습관에서 벗어나서 한 번 더 생각해보고 푸는 습관을 길러야 할 듯도 하다.