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

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

코딩테스트 연습 - 최소직사각형

 

1. 서론

 

이렇게 풀려도 되나? 싶은 level 1 문제

 

2. 문제 풀이

 

명함이 여러 개가 있고 그걸 넣어야 모두 넣을 수 있어야 하는 카드 지갑을 만들어야 한다. 이때 카드 지갑의 가로 x 세로의 값이 최소로 해야 하는데 그 최소로 했을 때의 값을 구하는 게 문제다.

나는 이렇게 단계를 나눴다.

 

1. 명함 여러 개의 가로, 세로 길이의 각각의 최댓값을 찾음
2. 가로, 세로의 최댓값 중 둘 중에 누가 더 큰 값인가를 찾음
3. 둘 중 큰 값을 저장해두고 나머지 하나 중(가로, 세로) 최댓값을 찾음
4. 이때 가로, 세로를 바꿔보는데 바꿀 때 원래의 값보다 바꾼 값이 더 크면 안 됨. 바꾼 값이 적은 경우에만 바꿈
5. 이 모든 과정을 거치고 최초의 가로, 세로 각각 최댓값을 곱했을 때보다 값이 작으면 그 값이 답이고 아니면 원래의 곱한 값이 답

이렇게 풀긴했는데 문제는 예전에 풀고 글은 지금 쓰는데 의문이 뭔가 더 예외의 케이스가 있을 것 같은데 이게 전부 케이스를 통과함

이 과정을 한 바퀴만 돌리면 뭔가 틀릴 것 같아서 while로 무한루프 문을 쓰긴 했지만 언제 브레이크가 제대로 작동하는지 나도 잘 모르겠는... 그때는 알고 이렇게 짠 건가? ㅎ 아마도 계속 최소의 가로 x값을 경신하는데 더 이상 갱신이 안되면 계속 최댓값이 똑같아지니까 그때 break가 걸리는 듯!!

 

3. 코드 설명

 

#include <vector>

using namespace std;

int solution(vector<vector<int>> sizes) {
    int answer = 0, row = 0, col = 0, m, idx, tmp, i, j, cnt = 0, x = 0;
    
    for (i = 0; i < sizes.size(); i++)
    {
        row = max(row, sizes[i][0]);
        col = max(col, sizes[i][1]);
    }
    
    if (row < col)
        m = col, idx = 0;
    else
        m = row, idx = 1;
    
    answer = m;
    
    cnt = row * col;
    
    while(1)
    {
        m = 0;
        for (i = 0; i < sizes.size(); i++)
            m = max(m, sizes[i][idx]);
        
        for (i = 0; i < sizes.size(); i++)
        {
            if (sizes[i][idx] == m)
            {
                tmp = sizes[i][0];
                sizes[i][0] = sizes[i][1];
                sizes[i][1] = tmp;
            }
        }
        
        m = 0;
        for (i = 0; i < sizes.size(); i++)
            m = max(m, sizes[i][idx]);
        
        x = answer * m;
        if (cnt > x)
            cnt = x;
        else
            break; 
    }
    
    return cnt;
}

 

위의 설명한 단계를 그대로 실행하는 코드.

가로의 값이 2차원 배열의 0번에, 세로의 값이 1번에 저장되어 있기 때문에 계산할 때 따로 지정해줬다.