코딩테스트 준비 - 최소직사각형

다시푸는 코딩 테스트 준비 일지

• 응시 사이트 : Programmers

• 문제 : 최소직사각형

• 사용언어 : C#

• 난이도 : 하 ~ 중

• 풀이시간 : 45m 48s

• 유형 : 문제이해, 2차원 배열

문제 설명

명함 지갑을 만드는 회사에서 지갑의 크기를 정하려고 합니다. 다양한 모양과 크기의 명함들을 모두 수납할 수 있으면서, 작아서 들고 다니기 편한 지갑을 만들어야 합니다. 이러한 요건을 만족하는 지갑을 만들기 위해 디자인팀은 모든 명함의 가로 길이와 세로 길이를 조사했습니다.

아래 표는 4가지 명함의 가로 길이와 세로 길이를 나타냅니다.

명함 번호 가로 길이 세로 길이 1 60 50 2 30 70 3 60 30 4 80 40

가장 긴 가로 길이와 세로 길이가 각각 80, 70이기 때문에 80(가로) x 70(세로) 크기의 지갑을 만들면 모든 명함들을 수납할 수 있습니다. 하지만 2번 명함을 가로로 눕혀 수납한다면 80(가로) x 50(세로) 크기의 지갑으로 모든 명함들을 수납할 수 있습니다. 이때의 지갑 크기는 4000(=80 x 50)입니다.

모든 명함의 가로 길이와 세로 길이를 나타내는 2차원 배열 sizes가 매개변수로 주어집니다. 모든 명함을 수납할 수 있는 가장 작은 지갑을 만들 때, 지갑의 크기를 return 하도록 solution 함수를 완성해주세요.

제한사항

• sizes의 길이는 1 이상 10,000 이하입니다.

  • sizes의 원소는 [w, h] 형식입니다.

  • w는 명함의 가로 길이를 나타냅니다.

  • h는 명함의 세로 길이를 나타냅니다.

  • w와 h는 1 이상 1,000 이하인 자연수입니다.

입출력 예

sizes result
[[60, 50], [30, 70], [60, 30], [80, 40]] 4000
[[10, 7], [12, 3], [8, 15], [14, 7], [5, 15]] 120
[[14, 4], [19, 6], [6, 16], [18, 7], [7, 11]] 133

입출력 예 설명

입출력 예 #1
문제 예시와 같습니다.

입출력 예 #2
명함들을 적절히 회전시켜 겹쳤을 때, 3번째 명함(가로: 8, 세로: 15)이 다른 모든 명함보다 크기가 큽니다. 따라서 지갑의 크기는 3번째 명함의 크기와 같으며, 120(=8 x 15)을 return 합니다.

입출력 예 #3
명함들을 적절히 회전시켜 겹쳤을 때, 모든 명함을 포함하는 가장 작은 지갑의 크기는 133(=19 x 7)입니다.

문제 풀이 접근

이 문제는, 가로x세로에서 모든 사각형을 포함하는 것 중 가장 작은 사각형을 만들면 되는 문제다.
문제에서 명함을 회전해서 포함한다. 라는 힌트를 줬기 때문에, 가로 < 세로 의 케이스는 무조건 가로와 세로를 바꾸어주면 된다.

문제를 잘못 읽어서 가로, 세로를 쌍으로보고 인덱스를 찾은 뒤 해당 인덱스 가로*세로 하면서 시간을 썻는데, 이 방법은 틀리다.
가로 세로는 따로 봐야한다.

이 문제의 플로우는,
1. 받은 2차원 배열을 체크하여 가로 < 세로의 케이스를 찾는다.
2. 그 다음 변경해서 list에 넣어준다.
3. 포함하는 것 중 가장 작은 최소 직사각형을 뽑는것이 주 목적이니, maxWidth, maxHeight 값은 Int32 표현범위중 제일 큰 값을 설정해놓는다.
4. list를 Loop 하면서 순회하는 원소 기준으로 list를 FindAll 함수를 이용해 찾는다.
이렇게 찾은 갯수가 현재 리스트 카운트와 동일하면 현재 원소는 가로 원소일땐 가로를 포함, 세로 원소일땐 세로를 포함한다.
리스트 내 고로 제일 큰 값이다.
5. 이 값 중 최소 직사각형을 뽑는 것이 목적이기 때문에 maxWidth >= Width 를 비교하여 현재 저장된 원소보다 작다면 값을 넣어준다.
6. 이렇게 구해낸 maxWidth, maxHeight를 사각형의 크기를 구하는 공식에 따라 곱해서 반환한다.

정답 작성 코드 (C#)

using System;
using System.Collections.Generic;

public class Solution {
    public int solution(int[,] sizes) {
             int answer = 0;
  List<Tuple<int, int>> list = new List<Tuple<int, int>>();

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

      if(width < height)
      {
          int temp = height;
          height = width;
          width = temp;
      }

      list.Add(new Tuple<int, int>(width, height));
  }

  int maxWidth = Int32.MaxValue;
  int maxHeight = Int32.MaxValue;

  for(int i = 0; i < list.Count; ++i)
  {
      var element = list[i];
      var width = element.Item1;
      var height = element.Item2;

      var countfst = list.FindAll(rhs => rhs.Item1 <= width).Count;
      var countsnd = list.FindAll(rhs => rhs.Item2 <= height).Count;

      if(list.Count == countfst)
      {
          if(maxWidth >= width)
              maxWidth = width;
      }

      if(list.Count == countsnd)
      {
          if (maxHeight >= height)
              maxHeight = height;
      }
  }

  answer = maxWidth * maxHeight;
  return answer;
    }
}

코드 결과