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

문제 출처

문제 출처 : 최소직사각형

문제 이해하기

• 다양한 모양과 크기의 명함을 모두 수납할 수 있으면서 동시에 크기는 최소한의 사이즈로 제작해야 하는 문제이다.

주요 조건 이해하기 ⭐️

주어진 입출력과 문제에 나와있는 규칙을 바탕으로 관찰을 해보면 4가지 정보가 나왔다.

1. 각 명함별 가로 * 세로 값 중 가장 큰 값은 아니다.
2. 마찬가지로 가장 큰 가로 * 가장 큰 세로의 값은 아니다.
3. 모든 경우의 수를 나열했을 때 1번에서 계산된 가장 큰 값보다 한 단계 큰 값은 아니다.
   • 이 경우 첫 번째 테스트 케이스는 말이 되지만, 두 번쩨 테스트 케이스는 성립이 말이 안된다.
4. 세로가 가로보다 큰 수만 서로의 위치를 바꾼 후 가장 큰 가로 * 가장 큰 세로의 결과값을 반환한다.

이 4가지의 정보 중 가장 말이 되는 내용은 4번이라고 생각했고, 직접 구현 스케치를 따봤다. (물론 1 ~ 3번까진 손으로 직접 그려보며 테스트한 내용이였다.)

		for (int i = 0; i < sizes.length; i++) {
			temp[i][0] = Math.max(sizes[i][0], sizes[i][1]);
			temp[i][1] = Math.min(sizes[i][0], sizes[i][1]);
		}

4번 항목을 기준으로 코드를 작성할 때 아래와 같은 순서로 코드를 작성하였다.

• 입력으로 들어오는 2차원 배열의 크기와 동일한 2차원 temp 배열을 만든다.
• 입력으로 들어온 2차원 배열을 순회하면서 temp 배열에 값을 집어넣는데, 이때 가로 위치에 대응되는 인덱스에는 가로, 세로 둘 중 큰 값을 집어넣고, 세로 위치에 대응되는 인덱스에는 가로, 세로 둘 중 작은 값을 집어넣는다.
• 이후 가로 값 중 가장 큰 값과 세로 값 중 가장 큰 값을 구한 후 곱한다.

최종 소스 파일

class Solution {
    public int solution(int[][] sizes) {
        int answer = 0;

		// 입력으로 들어오는 2차원 배열의 크기와 동일한 2차원 temp 배열을 만든다.
		int[][] temp = new int[sizes.length][sizes[0].length];

		// 입력으로 들어온 2차원 배열을 순회하면서 temp 배열에 값을 집어 넣는데, 
        // 이때 가로 위치에 대응되는 인덱스에는 가로, 세로 둘 중 큰 값을 집어넣고, 
        // 세로 위치에 대응되는 인덱스에는 가로, 세로 둘 중 작은 값을 집어넣는다.
		for (int i = 0; i < sizes.length; i++) {
			temp[i][0] = Math.max(sizes[i][0], sizes[i][1]);
			temp[i][1] = Math.min(sizes[i][0], sizes[i][1]);
		}

		// w에 최대값과 h의 최대값을 구한다.
		int w = Integer.MIN_VALUE;
		int h = Integer.MIN_VALUE;
		for (int i = 0; i < temp.length; i++) {
			if (temp[i][0] > w) {
				w = temp[i][0];
			}
		}

		for (int i = 0; i < temp.length; i++) {
			if (temp[i][1] > h) {
				h = temp[i][1];
			}
		}
		return w * h;
    }
}