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

풀이 날짜 : 2025.04.25
문제 유형 : 완전탐색
문제 제목 : 최소직사각형
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/86491

Intuition

• 명함의 가로,세로 크기가 담긴 배열이 주어질 때, 모든 명함을 담을 수 있는 지갑의 크기를 구해야 한다.
  • 각 명함은 회전이 가능하다. (가로, 세로를 바꿀 수 있다.)
• 각 명함마다 긴 쪽은 가로에, 짧은 쪽은 세로에 둔다고 생각해보면, 긴 쪽 중에 최댓값과 짧은 쪽 중에 최댓값을 구하면 모든 명함을 다 넣을 수 있다.
  • 문제 유형은 완전탐색(Brute force)라고 되어 있지만, 명함을 회전한 모든 조합을 시도하지 않고 그리디 알고리즘으로 푸는 게 더 효율적일 것 같다.

Approach

• 명함 크기에서 큰 쪽의 길이를 담을 배열(longs), 작은 쪽의 길이를 담을 배열(shorts)을 선언한다.
• sizes를 순회하면서 큰 쪽의 길이를 longs, 작은 쪽의 길이를 shorts에 담는다.
• longs의 최댓값, shorts의 최댓값을 곱한 값(= 지갑의 최대 크기)를 반환한다.

Complexity

• Time complexity : O(n)
  • sizes의 크기를 n이라고 할 때 sizes를 순회하므로 O(n)이다.
• Splace complexity : O(n)
  • longs, shorts 추가 배열을 생성했고 배열의 크기는 각각 n이므로 O(n)이다.

Code (JS)

function solution(sizes) {
    const longs = [];
    const shorts = [];

    for (const size of sizes) {
        longs.push(Math.max(...size));
        shorts.push(Math.min(...size));
    }

    return Math.max(...longs) * Math.max(...shorts);
}