20231115_기록_최소직사각형(프로그래머스)

오늘 한 것들

 

알고리즘 코드카타

 

오늘의 TIL은 알고리즘 코드카타에서 나왔던 문제로

최소직사각형

이라는 문제이다.

 

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

 

전체코드

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

public class Solution {
    public int solution(int[,] sizes) {
        int answer = 0;
        
        // 모든 명함을 담을 수 있는 크기의 지갑
        // 가로가 세로가 주어진 입력값에 대해서
        // 둘 중에 긴 쪽을 가로로 만들어서 w를 h로, h를 w로 만들어서
        // 이 중에 가장 큰 w와 h를 구한 뒤에 곱해서 answer로
        
        for (int i = 0; i < sizes.GetLength(0); i++)
        {
            if (sizes[i, 0] < sizes[i, 1])
            {
                int temp = sizes[i, 0];
                sizes[i, 0] = sizes[i, 1];
                sizes[i, 1] = temp;
            }            
        }
        
        List<int> col = new List<int>();
        List<int> row = new List<int>();
        
        for (int i = 0; i < sizes.GetLength(0); i++)
        {
            col.Add(sizes[i, 0]);
            row.Add(sizes[i, 1]);
        }
        
        int maxW = col.Max();
        int maxH = row.Max();
        
        answer = maxW * maxH;              
        
        return answer;
    }
}

 

 

문제에서는 명함과 지갑이라는 키워드를 사용해서 문제를 설명했는데,

간단히 요약하면 가로길이와 세로길이를 2차원 배열로 주어지면,

그 사각형들이 전부 들어갈 수 있는 사각형의 넓이를 구하는 문제로

 

예를 들어 input 값이

[[60, 50], [30, 70], [60, 30], [80, 40]] 로 주어지는 경우

위와 같은 사각형이 있다고 생각할 수 있다.

이 사각형들을 전부 포함할 수 있는 최소사각형을 구하는 문제로

로직을 생각해보면,

가로길이 중에서 가장 큰 값과 세로길이 중에서 가장 큰 값을 곱해서 사각형을 만들면 되는데,

위의 그림에서 가로길이 중에서 가장 큰 값은 8, 세로길이 중에서 가장 큰 값은 7로

답은 8 * 7로 표현할 수 있지만, 이는 최소직사각형이 아니다.

따라서 문제를 해결하기위해 약간의 조절을 해줘야되는데,

위의 그림을 기준으로하면 빨간색의 사각형을 90도 회전시키는 조절을 해주면된다.

그렇게되면 가로길이 중에서 가장 큰 값은 8, 세로길이 중에서 가장 큰 값은 5로

답은 8 * 5로 표현할 수 있고, 이가 최소직사각형이다.

 

즉, 주어진 배열에서 큰 수를 [i, 0]에, 작은 수를 [i, 1]에 위치하게 조절하는 과정이 필요한데

이를 코드로 나타내면

for (int i = 0; i < sizes.GetLength(0); i++)
        {
            if (sizes[i, 0] < sizes[i, 1])
            {
                int temp = sizes[i, 0];
                sizes[i, 0] = sizes[i, 1];
                sizes[i, 1] = temp;
            }            
        }

 

로 표현할 수 있다.

위의 for 문을 통해서 sizes에 있는 모든 원소들에 대해(i < sizes.GetLength(0))

[i, 0]과 [i, 1]을 비교하여 큰 수가 [i, 0]으로 작은 수가 [i, 1]에 위치하게 작업을 수행할 수 있다.

 

이후에는 각각에 최대값을 구하면 되는데, List를 이용하면

	List<int> row = new List<int>();
	List<int> col = new List<int>();
        
        for (int i = 0; i < sizes.GetLength(0); i++)
        {
            row.Add(sizes[i, 0]);
            col.Add(sizes[i, 1]);
        }

 

row와 col의 list를 만들어서

for 문을 돌면서 row에 sizes[i, 0] (가로) 값들을, col에 sizes[i, 1] (세로) 값들을 넣어줬다.

이후에 Max() 함수를 이용하여 아래와 같이 가로길이 중에서 가장 큰 값(maxW), 세로길이 중에서 가장 큰 값(maxH)를

구한 뒤에 이를 곱해서 최소직사각형의 넓이를 구했다.

	int maxW = row.Max();
        int maxH = col.Max();
        
        answer = maxW * maxH;              
        
        return answer;

 

 

 

이 문제에서 가장 크게 작용했던 부분은

주어진 배열에서 큰 값을 [i, 0]으로 작은 값을 [i, 1]로 이동시키는 과정으로

for 문을 돌면서 temp라는 값에 임시로 숫자를 저장하며 두 값을 변환시키는 방법을 채택했다.

2차원 배열으로 약간은 생소하게 느껴질 수 있는 개념과 함께

이 두가지가 특징인 문제였다.