[TIL] 최소 직사각형 구하기

문제

최소 직사각형을 구하려고 한다.
sizes = [[60, 50], [30, 70], [60, 30], [80, 40]]
위의 배열에서 가장 긴 가로 길이와 세로 길이가 각각 80, 70이기 때문에 80(가로) x 70(세로) 크기(= 5600)면 모든 직사각형을 포함할 수 있다. 하지만 sizes[2]를 가로로 눕힌다면([70,30]으로) 80(가로) x 50(세로) 크기(= 4000)로 모든 직사각형을 포함할 수 있다.
위와 같이 배열에서 모든 직사각형을 포함할 수 있도록 출력해보기.

제한사항

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

입출력 예

입출력 예 #2

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

입출력 예 #3

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

나의 코드

function solution(sizes) {
    let biggerSideMax = 0;
    let smallerSideMax = 0;
    let biggerSide = [];
    let smallerSide = [];
    
    for (let i = 0; i < sizes.length; i++) {
        if (sizes[i][0] > sizes[i][1]) {
            biggerSide.push(sizes[i][0]);
            smallerSide.push(sizes[i][1]); 
        } else {
            smallerSide.push(sizes[i][0]);
            biggerSide.push(sizes[i][1]); 
        }
    }

    biggerSideMax = Math.max(...biggerSide); // ... 스프레드 문법 사용
    smallerSideMax = Math.max(...smallerSide);
    
    return biggerSideMax * smallerSideMax;
}

문제를 풀 때 이해를 하지 못했지만, 힌트들을 보면서 감을 잡을 수 있었다.
1. 직사각형이므로 긴 변과 작은 변이 있다. 이 둘을 구분한다.
2. 배열을 선언하고 긴 변만 따로, 작은 변만 따로 배열에 담는다.
3. 긴 변에서 가장 큰 값, 작은 변에서 가장 큰 값을 빼내서 곱한다.

배열을 선언하지 않고도 문제를 해결한 풀이

function solution(sizes) {
  let width = 0;
  let height = 0;

  for (let i = 0; i < sizes.length; i++) {
    if (sizes[i][0] > sizes[i][1]) {
      if (width < sizes[i][0]) width = sizes[i][0];
      if (height < sizes[i][1]) height = sizes[i][1];
    } else {
      if (width < sizes[i][1]) width = sizes[i][1];
      if (height < sizes[i][0]) height = sizes[i][0];
    }
  }

  return width * height;
}