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

문제

명함의 가로, 세로 길이가 주어졌을 때

모든 명함을 담을 수 있는 가장 작은 명함 지갑의 넓이를 구하라

 

접근 방식

	가로	세로
1	60	50
2	30	70
3	60	30
4	80	40

 

만약 명함의 길이가 위와 같이 주어졌다면

가로의 가장 긴 길이와 세로의 가장 긴 길이를 찾아

지갑을 만들면 모든 명함을 넣을 수 있다.

 

하지만 문제에서 구해야 하는 것은 지갑의 최소 넓이이기 때문에

생각을 좀 달리해야 한다.

 

가장 긴 가로와 세로 길이의 지갑이면 명함을 모두 넣을 수 있으니

명함을 90도 회전하는 경우에는 좀 더 작은 면적의 지갑으로도

명함을 모두 보관할 수 있다.

 

	가로	세로
1	60	50
2	70	30
3	60	30
4	80	40

 

바로 위와 같이 가로보다 세로가 긴 경우 둘의 길이를 바꿔준 후에 (90도 회전)

가로와 세로의 가장 큰 값을 구하면 된다.

 

입력의 크기가 작은 문제이기 때문에 완전 탐색을 이용해

주어진 배열을 순회하며 가로와 세로의 길이를 확인한 후에

세로가 더 큰 경우 바꿔주고 각각의 최대 길이를 갱신해준다.

 

풀이

public class Main {

	public static void main(String[] args) {
		System.out.println(solution(
			new int[][]{{60, 50}, {30, 70}, {60, 30}, {80, 40}}
		));
		System.out.println(solution(
			new int[][]{{10, 7}, {12, 3}, {8, 15}, {14, 7}, {5, 15}}
		));
		System.out.println(solution(
			new int[][]{{14, 4}, {19, 6}, {6, 16}, {18, 7}, {7, 11}}
		));
	}

	private static int solution(int[][] sizes) {
		int max1 = 0;
		int max2 = 0;

		for (int i = 0; i < sizes.length; i++) {
			int left = sizes[i][0];
			int right = sizes[i][1];

			if (left > right) {
				sizes[i][0] = right;
				sizes[i][1] = left;
			}

			max1 = Math.max(sizes[i][1], max1);
			max2 = Math.max(sizes[i][0], max2);
		}

		return max1 * max2;
	}
}