[프로그래머스] Level1. 최소직사각형

문제 설명과 입출력 예시는 다음과 같다.

먼저 기본적인 뼈대를 잡아보았다.

function solution(sizes) {
    let minWidth = 0;  // 수납할 수 있는 최소 가로 길이
    let minHeight = 0;  // 수납할 수 있는 최소 세로 길이
    
    // 몇 번째인지가 중요하지 않기 때문에 for...of 사용
    for(let size of sizes) {
			// 코드 작성(최소 가로, 세로 길이 구하기)
    }
    
		return minWidth*minHeight;  // 최소의 지갑 크기
}

최소 가로 길이, 최소 세로 길이라고 적혀있지만 실제로 가장 작은 수를 뜻하기 보다는 모든 명함을 수납할 수 있는 길이 중 가장 작은 길이! 즉, 가장 큰 값이 들어가게 될 것이다.

function solution(sizes) {
    let minWidth = 0;
    let minHeight = 0;
    
    for(let size of sizes) {
			const width = size[0]  // 가로
			const height = size[1]  // 세로
			
	//  배열을 돌면서 가로, 세로의 가장 큰 값 받아오기		
      minWidth = Math.max(minWidth, width)
      minHeight = Math.max(minHeight, height)
    }
    
		return minWidth*minHeight;
}

이제 대부분의 코드는 작성 되었다. 그러나 문제에서 가장 중요한 부분은 명함을 가로로 눕혀 수납할 수도 있다는 점이다.

이해를 돕기 위한 이미지를 첨부해보겠다.

위 사진을 보면 1, 3, 4번 명함의 경우 긴 면이 가로에 위치해있지만 2번 명함은 긴 면이 세로에 위치해있다(정렬 x). 이 상태로 모든 명함을 한 지갑에 넣기 위해선
<2번 명함의 세로길이 * 4번 명함의 가로길이> 크기의 지갑이 필요할 것이다.

하지만 여기서 2번 명함을 눕혀 긴 면을 한쪽 방향(가로)에 몰아준다면,

훨씬 작은 크기의 지갑으로 모든 명함을 수납할 수 있게 될 것이다.

따라서 size의 값을 내림차순 또는 오름차순으로 정렬하여 한쪽 방향에 큰 값을 몰아주려 한다.

function solution(sizes) {
    let minWidth = 0;
    let minHeight = 0;
    
    for(let size of sizes) {
	    size.sort((a, b) => b - a)  // 내림차순 정렬(큰 값이 가로)
    
			const width = size[0]
			const height = size[1]
			
      minWidth = Math.max(minWidth, width)
      minHeight = Math.max(minHeight, height)
    }
    
		return minWidth*minHeight;
}

이렇게 하면 문제에서 요구한대로 모든 명함을 수납할 수 있는 가장 작은 지갑의 크기를 리턴할 수 있다.