프로그래머스 - 최소직사각형

 이차원 배열 sizes를 받아 배열 안에 저장된 값들 중 모든 명함 크기를 수용할 수 있는 크기 중 가장 작은 크기를 계산하여 반환하는 함수이다. 코드를 보며 설명하도록 하겠다.

 현재 기준 역대 level 1 프로그래머스 문제들 중 가장 긴 코드이다. 우선 어떻게 solution을 내려고 했는지에 대해서 코드의 큰 틀을 설명하도록 하겠다. 모든 경우의 수 즉, 모든 크기의 명함을 수용하기 위해서는 가장 큰 값을 구해야 한다. 그 이유는 문제의 설명에 명함을 눕히는 것이 가능하다고 되어있는데, 이점을 이용해 지갑의 크기를 줄일 수 있다. 이해를 돕기 위해 첫 번째 입출력 예를 통해 예시를 보이겠다. 첫 번째 입출력은 [[60, 50], [30, 70], [60, 30], [80, 40]]이고, 가장 큰 값은 80이다. 만약 이 상태에서 바로 모든 명함을 수용할 수 있는 지갑을 만든다면 80 x 70(5,600)의 크기가 될 것이다. 하지만 명함을 눕히는 방법을 통해 지갑을 80 x 50(4,000)의 크기까지 줄일 수가 있다. 방법은 간단하다. 모든 요소 중 가장 큰 값은 80이기 때문에 아무리 명함을 눕혀도 최대 길이(가로이던 세로이던 관계없다)가 80을 넘을 수는 없다. 그렇다면 가로의 길이던 세로의 길이던 무조건 한 자리는 80이 될 테고 다른 자리의 길이가 최종 지갑의 크기를 결정하게 된다. 그렇기 때문에 다른 한쪽의 길이를 눕히는 방법을 통해 최대한 작은 것으로 바꾸어야 한다. 어떻게 바꾸어야 할까. 잘 생각해보면 이렇다. 우선 가장 큰 요소인 80은 sizes [3][0]에 위치해있다. 그렇다면 동일한 sizes [i][0] 라인에는 어떤 수가 와도 이쪽 라인 지갑의 길이는 무조건 80이다. 그렇기 때문에 최대한 이 쪽에 큰 숫자들을 배치해야 다른 한쪽이 최대한 작은 숫자들만 모이게 되어 가장 작은 지갑을 만들 수 있게 된다. 그래서 80을 가지고 있는 3행의 요소들을 제외하고 나머지 0, 1, 2행의 요소들 중 0열의 값보다 1열의 값이 더 크다면 눕혀 1열에 작은 수가 가게끔 배치를 해주게 되면 [[60, 50], [70, 30], [60, 30], [80, 40]]으로 바뀌게 된다. 이때 0열의 가장 큰 값은 80, 1열의 가장 큰 값은 50이 되어 모든 명함을 수용할 수 있는 80 x 50(4,000) 크기의 지갑을 만들 수 있게 된다.