최소직사각형 - 프로그래머스, c++

 

 

- 문제 풀이

"완전 탐색"을 이용하는 문제였다.

먼저 완전 탐색에 대해 공부해보았다.

완전 탐색은 모든 경우의 수를 고려하는 조금은 무식한(?) 방법이다.

완전 탐색의 종류에는

1. 단순 Brute-Fore 방법

2. 비트마스크

3. 재귀 함수

4. 순열

5. BFS/DFS

정도가 있다.

(참고: https://rebro.kr/59)

 

 

- 코드

제출한 코드는 다음과 같다.

마냥 큰 수들끼리의 곱을 찾는 것이 아니기 때문에 가로와 세로의 값을 비교해 때에 가로보다 세로가 더 크다면 가로쪽에 더 큰 수를 몰아주도록 하는 코드가 필요했다.

(세로 쪽에 더 큰 수를 몰아도 상관없음, 한 쪽에 더 큰 수를 몰아야 함)

#include <string>
#include <vector>
using namespace std;

int solution(vector<vector<int>> sizes) {
    int answer = 0;
    
    int widthmax = 0;
    int heightmax = 0;
    
    for(int i=0; i<sizes.size(); i++) {
        int temp;
        if( sizes[i][0]<sizes[i][1] ) {
            temp = sizes[i][0];
            sizes[i][0] = sizes[i][1];
            sizes[i][1] = temp;
        }
        if( widthmax<sizes[i][0] ) {
            widthmax = sizes[i][0];
        }
        if( heightmax<sizes[i][1] ) {
            heightmax = sizes[i][1];
        }
    }
    
    answer = widthmax*heightmax;
    
    return answer;
}