[프로그래머스] 최소직사각형(C++)

안녕하세요! 오늘은 코딩테스트 문제 중 하나인 "최소직사각형" 문제를 해결하는 방법에 대해 설명하려고 합니다. 문제는 명함 지갑을 만드는 회사에서 다양한 모양과 크기의 명함들을 모두 수납할 수 있으면서, 작고 휴대하기 편한 지갑을 만드는 것에 관한 것입니다. 문제를 해결하는 과정과 코드를 자세히 알아보겠습니다.

문제링크 : 

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

프로그래머스

문제 개요

이 문제는 명함 지갑을 만드는 회사에서 다양한 모양과 크기의 명함들을 모두 수납할 수 있으면서, 작고 휴대하기 편한 지갑을 만드는 것에 관한 것입니다. 문제에서는 명함의 가로 길이와 세로 길이가 2차원 배열 형태로 주어지며, 이 명함들을 모두 수납할 수 있는 가장 작은 지갑의 크기를 구하는 것이 목표입니다.

문제 해결 전략

이 문제의 핵심은 각 명함을 회전시켜 가로와 세로 길이를 최대한 효율적으로 사용하는 것입니다. 명함은 회전시킬 수 있으므로, 각 명함의 긴 쪽을 가로로, 짧은 쪽을 세로로 고려하여 가장 긴 가로 길이와 세로 길이를 찾아야 합니다.

구현 단계:

1. 명함의 회전: 각 명함에 대해 긴 쪽을 가로 길이로, 짧은 쪽을 세로 길이로 설정합니다.
2. 최대 길이의 계산: 모든 명함 중에서 가장 긴 가로 길이와 가장 긴 세로 길이를 찾습니다.
3. 지갑의 크기 계산: 가장 긴 가로 길이와 세로 길이를 곱하여 지갑의 크기를 계산합니다.

코드 구현

#include <string>
#include <vector>
#include <bits/stdc++.h>
using namespace std;

// sizes 배열에 담긴 명함의 크기를 기반으로 최소 직사각형의 크기를 반환하는 함수
int solution(vector<vector<int>> sizes) {
    int answer = 0; // 최종 결과를 저장할 변수
    int max_x = 0; // 가장 긴 가로 길이를 저장할 변수
    int max_y = 0; // 가장 긴 세로 길이를 저장할 변수
    vector<pair<int,int>> table; // 가로와 세로 길이를 저장할 pair 형식의 벡터

    // sizes 벡터를 순회하면서 가로와 세로 길이를 비교하여 긴 쪽을 가로로 설정
    for(int i = 0; i < sizes.size(); i++){
        if(sizes[i][0] > sizes[i][1]){
            table.push_back({sizes[i][0], sizes[i][1]}); // 가로가 세로보다 길 경우
        }
        else{
            table.push_back({sizes[i][1], sizes[i][0]}); // 세로가 가로보다 길 경우
        }
    }

    // table 벡터를 순회하면서 가장 긴 가로와 세로 길이를 찾음
    for(auto it : table){
        if(it.first > max_x){
            max_x = it.first; // 가장 긴 가로 길이 업데이트
        }
        if(it.second > max_y){
            max_y = it.second; // 가장 긴 세로 길이 업데이트
        }
        // 현재까지 찾은 가장 긴 가로와 세로 길이 출력 (디버깅용)
        cout << " Max X : " << max_x << " Max Y : " << max_y << "\n";
    }

    answer = max_y * max_x; // 최종 지갑의 크기 계산
    return answer; // 계산된 크기 반환
}

코드 설명

• 각 명함의 가로와 세로 길이를 비교하여, 긴 쪽을 가로(width), 짧은 쪽을 세로(height)로 설정합니다.
• 모든 명함을 순회하면서, 지금까지 발견된 가장 긴 가로와 세로 길이를 업데이트합니다.
• 최종적으로 가장 긴 가로와 세로 길이의 곱을 반환하여, 지갑의 최소 크기를 계산합니다.

결론

이 문제의 해결은 각 명함을 효율적으로 회전시켜 최대 길이를 계산하는 것에 있습니다. 이 접근 방식을 통해, 모든 명함을 수납할 수 있는 최소 크기의 지갑을 만들 수 있습니다. 문제의 핵심은 명함의 회전 가능성을 인식하고, 그에 따라 최대 길이를 동적으로 계산하는 것입니다.