[프로그래머스] 최소직사각형 (Lv.1)
문제 링크
문제 설명
명함 지갑을 만드는 회사에서 지갑의 크기를 정하려고 합니다. 다양한 모양과 크기의 명함들을 모두 수납할 수 있으면서, 작아서 들고 다니기 편한 지갑을 만들어야 합니다.
각 명함의 가로 길이와 세로 길이를 나타내는 2차원 배열 sizes가 매개변수로 주어집니다. 모든 명함을 수납할 수 있는 가장 작은 지갑을 만들 때, 지갑의 크기를 return 하도록 solution 함수를 완성해주세요.
제한사항
- sizes의 길이는 1 이상 10,000 이하입니다.
- sizes의 각 원소는 [w, h] 형식입니다.
- w는 명함의 가로 길이를 나타냅니다.
- h는 명함의 세로 길이를 나타냅니다.
- w와 h는 1 이상 1,000 이하인 자연수입니다.
내 풀이
모든 명함을 긴 쪽이 가로(card[0]), 짧은 쪽이 세로(card[1])가 되도록 방향을 통일한다.
그 후 모든 명함의 가로 최댓값과 세로 최댓값을 구해 곱하면 최소 지갑 크기가 된다.
#include <string>
#include <vector>
using namespace std;
int solution(vector<vector<int>> sizes) {
int w = 0;
int h = 0;
for(auto& card : sizes)
{
if(card[0] < card[1])
swap(card[0], card[1]);
}
for(auto& card : sizes)
{
if(w < card[0]) w = card[0];
if(h < card[1]) h = card[1];
}
return w * h;
}
시간복잡도 분석
- 방향 통일 반복문: O(N)
- 최댓값 탐색 반복문: O(N)
- 전체: O(N), N = sizes 크기 (최대 10,000)
N ≤ 10,000이므로 충분히 통과 가능하다.
오답노트
처음에는 어떻게 접근해야 할지 감이 잡히지 않았다.
핵심 아이디어는 모든 명함의 방향을 통일하는 것이다. 명함은 회전이 가능하므로, 긴 쪽을 항상 가로로 맞추면 지갑의 가로 = 모든 명함 가로의 최댓값, 세로 = 모든 명함 세로의 최댓값으로 단순화된다.
방향을 통일하지 않고 그냥 최댓값을 구하면 불필요하게 큰 지갑이 나오게 된다.