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

▪︎ 문제

---

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

▪︎ 알고리즘 설계

---

• 이 문제의 핵심은 직사각형의 가로/세로의 값이 고정적인게 아니라 가로, 세로 값이 서로 바뀔 수 있다는 것.
  • 따라서 기준이 필요함.
• 가로와 세로 중, 더 긴 쪽을 가로(세로로 맞춰도 괜찮다.)로 맞춘 뒤 가로/세로 각각의 최댓값을 구하여 곱하면 된다.

▪︎ 코드

---

import java.util.*;

class Solution {
    public int solution(int[][] sizes) {
        int maxW = 0; // 지갑 가로의 최댓값
        int maxH = 0; // 지갑 세로의 최댓값

        for (int i = 0; i < sizes.length; i++) {
            int w = Math.max(sizes[i][0], sizes[i][1]); // 긴 변을 가로로
            int h = Math.min(sizes[i][0], sizes[i][1]); // 짧은 변을 세로로
            maxW = Math.max(maxW, w);
            maxH = Math.max(maxH, h);
        }

        return maxW * maxH;
    }
}

▪︎ 시간복잡도

---

O(N)

▪︎ 틀린 이유

---

import java.util.*;

class Solution {
    public int solution(int[][] sizes) { // 모든 명함의 가로, 세로 길이 배열
        
        int[] widths = new int[sizes.length];
        int[] heights = new int[sizes.length];
        
        for(int i = 0; i < widths.length; i++) {
            widths[i] = sizes[i][0];
            heights[i] = sizes[i][1];
        }
        
        Arrays.sort(widths);
        Arrays.sort(heights);

        return widths[widths.length-1] * heights[heights.length-1]; // 모든 명함을 수납할 수 있는 가장 작은 지갑의 크기
    }

• 배열 크기 오해
  • sizes[0].length는 열의 개수(항상 2), 명함 개수는 sizes.length로 잡아야 한다.
  • 지금처럼 하면 widths, heights의 길이가 2가 되어 명함이 2장을 초과하면 대부분을 무시하거나, 명함이 1장이면 IndexOutOfBounds가 날 수 있다.
• 회전(정규화) 누락
  • 각 명함은 회전이 가능하므로, 긴 변을 가로로, 짧은 변을 세로로 맞추는 정규화가 필수
  • 정규화 없이 그냥 widths와 heights를 따로 모으면, 최소 넓이를 보장할 수 없다.
• 쌍 관계(pairing) 파괴
  • widths와 heights를 각각 정렬한 뒤 최댓값을 곱하는 방식은, (가로, 세로)의 쌍 관계를 깨뜨린다.
  • 반례: [[2, 100], [100, 2]]
    • 정답: 각 명함을 (100,2)로 정규화 → 가로=100, 세로=2 → 넓이=200
    • 잘못된 방식: max(widths)=100, max(heights)=100 → 넓이=10,000 (과대추정)
• 불필요한 정렬
  • 최댓값만 필요하므로 정렬 자체가 불필요. 정렬은 O(N log N)로 성능만 낭비.

▪︎ 느낀점 / 기억할 정보

---

• 회전 가능 문제는 정규화로 단순화 하자.
  • 각 원소를 공통 기준으로 바꿔 놓으면 이후 처리가 쉬워 진다.
• 최댓값 하한 논리
  • 어떤 컨테이너의 최소 크기를 구할 떄, 포함해야 하는 대상들의 치수가 주는 하한을 먼저 생각하면 설계가 깔끔해진다.
• 문제 꼼꼼히 읽기
  • “회전 가능” 같은 한 줄이 풀이를 완전히 바꾼다. 문제의 전제/제약을 반드시 코드에 반영한다.
• 2차원 배열 헷갈리지 않기
  • arr.length → 행 수
  • arr[i].length → i행의 열 수