24/07/30 알고리즘 문제

오늘부터는 코딩 풀이에 대해 간단한 설명을 덧붙이려고 한다.

시간이 나면 이전에 작성했던 것들도 천천히 설명을 추가할 예정이다.

 

1. 최소직사각형(https://school.programmers.co.kr/learn/courses/30/lessons/86491)

 

해당 문제는 2차원의 배열로 주어진 값을 통해, 최소직사각형을 만드는 문제이다.

가로	세로
60	50
30	70
60	30
80	40

다음과 같이 주어졌을 때, 가장 긴 가로와 세로가 각각 80, 70이기 때문에 5600이 나올 수 있다.

하지만 [30, 70]의 가로세로 방향을 바꾸면 다음과 같이 된다.

 

가로	세로
60	50
70	30
60	30
80	40

이 경우 가장 긴 가로와 세로는 80, 50이기 때문에 최소직사각형은 4000이 된다.

 

그 외에 해당 문제의 입출력 예를 보았을 때, 이 문제를 풀기 위한 방법은

1. 가로 세로의 값을 가로 = 큰 숫자, 세로 = 작은 숫자로 정렬한다.
2. 정렬된 가로, 세로 중에서 각각 가장 큰 숫자를 고른다.
3. 골라진 값들을 곱하여 답을 구한다.

라고 생각했다.

 

그래서 C언어에서는 먼저 배열을 정렬했다. 큰 값은 전부 가로로 돌리고, 작은 값은 전부 세로로 돌렸다.

그리고 가로 세로 중 각각 큰 가장 큰 값을 고르고, 해당 값들을 곱하여 답을 구했다.

// c언어
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

int solution(int** sizes, size_t sizes_rows, size_t sizes_cols) {
    int answer = 0;
    int max_r = 0, max_c = 0;
    
    for(int i=0; i<sizes_rows; i++)
    {
        if(sizes[i][0] < sizes[i][1])
        {	// 배열 정렬
            int temp = sizes[i][0];
            sizes[i][0] = sizes[i][1];
            sizes[i][1] = temp;
        }
        
        // 최대값 구하기
        if(max_r < sizes[i][0])
            max_r = sizes[i][0];
        if(max_c < sizes[i][1])
            max_c = sizes[i][1];
    }
    
    answer = max_r * max_c;
    
    return answer;
}

 

JS에서는 방법을 조금 다르게 했다.

정렬 과정은 생략하고, 새로운 배열 2개를 만들어 가로 세로를 비교해 큰 값은 max 배열로, 작은 값은 min 배열로 push()했다.

그리고 각 배열에서 가장 큰 값을 고르고, 해당 값들을 곱해 답을 구했다.

// js
function solution(sizes) {
    var answer = 0, max_r, max_c;
    var max = [], min = [];
    
    sizes.forEach(function(sizes) {
        [one, two] = sizes;
        max.push(Math.max(one, two));
        min.push(Math.min(one, two));
    })
    
    max_r = Math.max.apply(null, max);
    max_c = Math.max.apply(null, min);
    
    answer = max_r * max_c;
    
    return answer;
}