[알고리즘] 최소직사각형

출처: 프로그래머스 코딩 테스트 연습

문제 요약

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

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

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

입출력 예시

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

제한 사항

• sizes의 길이는 1 이상 10,000 이하입니다.
  • sizes의 원소는 [w, h] 형식입니다.
  • w는 명함의 가로 길이 h는 명함의 세로 길이를 나타냅니다.
  • w와 h는 1 이상 1,000 이하인 자연수입니다.

문제 풀이

난이도 1인데 왜 어렵게 느껴지지... 게다가 완전 탐색이라는 주제로 검색해서 나온 문제여서 더욱 헷갈렸던 문제였다. 예시를 보고 처음에 생각한 방식은

1. 우선 현재 sizes 배열에서 w와 h의 최대값을 사용해서 전체 면적을 구한다.
2. 각 배열들을 순회하면서 w와 h의 위치를 변경한다.
3. 변경 후 w와 h의 최대값을 사용해서 전체 면적을 구한다
4. 모든 최대값들 중에서 가장 작은 값을 반환한다.

이런 생각을 갖고 처음에 루프를 만들어서 하나씩 자리를 교체하고 면적을 구했다. 1번 테스트는 통과했지만 2번, 3번 테스트에서 실패하였고 원인을 찾다 보니 내 코드에 의하면 2번 테스트의 정답은 180이 되어야 했다. 풀이 방법이 잘못 되었다는 것을 알았고 다른 사람들의 풀이 방법을 찾아보게 되었다.ㅠ

function solution(sizes) {
  const big = [];
  const small = [];
  
  sizes.map((size) => {
    if(size[0] > size[1]) {
      big.push(size[0]);
      small.push(size[1]);
    } else {
      big.push(size[1]);
      small.push(size[0]);
    }
  });
  
  return Math.max(...big) * Math.max(...small);

결과적으로 이 문제는 한 명함의 w, h 중 큰 숫자는 big이라는 배열에 작은 숫자는 small이라는 배열에 저장하고 각각 big, small에서 가장 큰 최대값들의 합을 구하는 문제였다.

마무리

level1 문제라서 쉽게 생각했던것도 있고 정답이라고 생각한 코드가 실패하자 쉽게 멘붕이 와서 다른 사람 코드를 찾아보게 되었다... 문제를 제대로 이해하는 능력이 아직도 부족하다는 생각이 든다.