[프로그래머스 / Java] Lv.1 최소직사각형 - 연습 문제 (1) with ChatGPT

 

📘 연습 문제  :  포스터 보관 파일의 최소 크기

 

문제 설명

여러 장의 포스터를 하나의 파일에 보관하려고 합니다.
각 포스터는 가로와 세로 길이가 주어지며,
포스터는 회전해서 넣을 수 있습니다.

모든 포스터를 담을 수 있는 파일의 최소 가로 × 세로 크기를 구하세요.

---

입력

• posters: 2차원 정수 배열
  • posters[i][0] : i번째 포스터의 가로 길이
  • posters[i][1] : i번째 포스터의 세로 길이

---

출력

• 모든 포스터를 담을 수 있는 파일의 최소 넓이

---

제한 사항

• 1 ≤ posters.length ≤ 10,000
• 1 ≤ posters[i][0], posters[i][1] ≤ 1,000

---

예시

posters = [[5, 7], [3, 4], [6, 2]]

---

설명

• 각 포스터를 회전 가능하므로
  • (7,5), (4,3), (6,2) 형태로 통일
• 최대 가로 = 7
• 최대 세로 = 5
• 결과 = 7 × 5 = 35

---

핵심 사고

• “회전 가능” → 항상 큰 값 / 작은 값으로 정규화
• 전체를 감싸는 최소 크기 → 각 축의 최댓값
• 불필요한 정렬 ❌
• 한 번의 순회 ⭕ → O(N)

---

스스로 점검 질문

• 왜 각 포스터를 (max, min) 형태로 바꾸는 게 최적인가?
• 만약 회전이 불가능하다면 이 알고리즘은 성립할까?
• 이 문제에서 정렬을 쓰면 시간 복잡도는 어떻게 변할까?

---

Algorithm

1. 파일의 가로·세로 최대값을 저장할 변수를 초기화한다.

• maxWidth, maxHeight를 0으로 설정한다.

2. 포스터는 회전 가능하므로 긴 변 → 가로, 짧은 변 → 세로 로 통일한다.

3. 현재 포스터 기준으로 전체 최대 가로·세로를 갱신한다.

• maxWidth에는 지금까지의 가장 긴 변 중 최댓값을 저장한다.
• maxHeight에는 지금까지의 가장 짧은 변 중 최댓값을 저장한다.

4. 모든 포스터를 담을 수 있는 최소 넓이를 계산한다.

• maxWidth × maxHeight를 반환한다.

---

Code

class Solution {
    public int solution(int[][] posters) {

        // 모든 포스터를 담을 수 있는 파일의 가로 최대값
        int maxWidth = 0;

        // 모든 포스터를 담을 수 있는 파일의 세로 최대값
        int maxHeight = 0;

        // 각 포스터를 하나씩 확인
        for (int i = 0; i < posters.length; i++) {

            // 현재 포스터의 두 변 중 더 긴 쪽
            int longer = Math.max(posters[i][0], posters[i][1]);

            // 현재 포스터의 두 변 중 더 짧은 쪽
            int shorter = Math.min(posters[i][0], posters[i][1]);

            // 가로는 지금까지 나온 긴 변 중 가장 큰 값으로 갱신
            maxWidth = Math.max(maxWidth, longer);

            // 세로는 지금까지 나온 짧은 변 중 가장 큰 값으로 갱신
            maxHeight = Math.max(maxHeight, shorter);
        }

        // 파일의 최소 넓이 = 가로 최대값 × 세로 최대값
        return maxWidth * maxHeight;
    }
}

---

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/86491

프로그래머스