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

링크: https://school.programmers.co.kr/learn/courses/30/lessons/86491?language=cpp

프로그래머스

 

1. 문제 접근

이 문제의 핵심은 명함을 회전할 수 있다는 점이다.

 

예를 들어

[30,70] 이 명함은 회전하면 [70,30] 으로도 사용 가능

따라서 모든 명함을 담기 위해서는 다음 기준으로 정리해야 한다.

1. 각 명함에서 긴 변을 가로로 통일 => 중요
2. 짧은 변을 세로로 통일 => 중요
3. 가로 중 최댓값, 세로 중 최댓값을 구함

즉, 모든 명함을 같은 방향으로 맞춘 뒤 가장 큰 가로와 세로만 고려하면 된다. => 핵심 idea

 

2. 풀이(2개)

• 1번 풀이 swap 사용
  

  #include <string>
  #include <vector>
  #include <algorithm>
  
  using namespace std;
  
  int solution(vector<vector<int>> sizes) {
      int h = 0;
      int w = 0;
      
      for(int i = 0; i < sizes.size(); i++){
         // 명함 방향 통일  => 항상 큰 값을 앞에 오도록 SWAP
          if(sizes[i][1] > sizes[i][0]){ 
              swap(sizes[i][0], sizes[i][1]); // 큰값이 size[i][0] 자리에 오도록!
          }
          
          h = max(h, sizes[i][0]); // 긴 변 중 최대값
          w = max(w, sizes[i][1]); // 짧은 변 중 최대값
      }
      
      return h * w;
  }

• 2번 풀이 swap 사용 x
  

  #include <string>
  #include <vector>
  #include <iostream>
  
  using namespace std;
  
  int solution(vector<vector<int>> sizes)
  {
      int answer=0;
  
      int w=0, h=0;
      for(int i=0; i<sizes.size(); i++)
      {
          w=max(w,min(sizes[i][0],sizes[i][1])); // w=작은값 중 가장 큰 값
          h=max(h,max(sizes[i][0],sizes[i][1])); // h=큰값 중 가장 큰 값
      }
  
      // 어차피 위의 for문 통해서 큰 값은 전부 h쪽으로 몰리게 됨
      answer=w*h;
  
      return answer;
  }

   

 

3. 문법

• vector<vector<int>>
  (참고) 이중백터 설명 문제 [프로그머스] 행렬의 덧셈 C++ (Lv.1)
  

  vector<vector<int>> sizes;

  • 2차원 배열과 같은 구조
  • sizes[i][0], sizes[i][1] 형태로 접근 가능
    
    
• 3-2. swap()
  

  swap(a, b);
  

  • 두 변수의 값을 서로 바꿔주는 함수
  • 여기서는 가로/세로를 뒤집는 용도로 사용
• 3-3. max()
  (참고) [C++] max() 함수란?
  

  max(a, b);
  

  • 두 값 중 더 큰 값을 반환
  • 반복문에서 최댓값 갱신할 때 필수

 

4. 최종 요약

이 문제는 복잡해 보이지만 핵심은 하나다. "모든 명함을 같은 방향으로 맞춘다"

그 후에는 단순하다.

1. 긴 변끼리 비교 ->  최대값
2. 짧은 변끼리 비교 ->  최대값
3. 두 값을 곱하면 끝

최소 직사각형 = (긴 변 최대값) × (짧은 변 최대값)