알고리즘🅰/프로그래머스

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

개발조각 2022. 2. 14. 23:22
728x90
반응형

2021.11.09에 푼 문제입니다.

 

프로그래머스 코딩 테스트 연습에서 Level 1이 3페이지가 있는데
드디어 첫 번째 페이지는 끝냈고 두 번째 페이지를 풀게 되었습니다.~~ 예이~~~!!🤩

 

본론으로 돌아와서 이번 문제는 쉬운 편에 속하는 것 같고, 어떻게 더 간단하게 쓰는지에 따라 다른 것 같다는 생각이 들어요.

해결방안 보기 전에 어떻게 풀었는지에 대해 설명하자면,

 

이 문제는 다양한 모양과 크기의 명함들을 모두 수납할 수 있으면서, 작아서 들고 다니기 편한 지갑을 만들어야 하는 문제인데

문제 설명을 쭉 읽다 보면 "명함을 가로로 눕혀 수납한다면"이라는 문장이 나옵니다.
이 말은 "가로, 세로를 고정을 할 필요가 없다"는 겁니다.

입출력 예에서 테스트 1을 보시면

가장 긴 가로길이와 세로 길이는 각각 80, 70입니다.

그러므로 80(가로) x 70(세로) 크기의 지갑을 만들면 모든 명함들을 수납할 수 있습니다. 

 

여기서 위에 설명에서 "가로, 세로를 고정을 할 필요가 없다"라고 했었죠?

가로, 세로 길이가 아닌 큰 수 작은 수로 나열해보면

  • 첫 번째 : 가로, 세로 중 큰 수
  • 두 번째 : 가로, 세로 중 작은 수
명함번호 첫번째 수(가로, 세로 중 큰수) 두번째 수(가로, 세로 중 작은 수)
1 60 50
2 70 30
3 60 30
4 80 40

이렇게 됩니다.

그럼 첫 번째 수에서 가장 큰 수는 80, 두번째 수에서 가장 큰수는 50이 됩니다.

  • 가로 : 60, 70, 60, 80 -> 가로 최댓값 : 80
  • 세로 : 50, 30, 30, 40 -> 세로 최댓값 : 50

그래서 80(가로) x 50(세로) = 4000 크기의 지갑으로 모든 명함들을 수납할 수 있게 됩니다.

 

여기서 알 수 있는 점은
명함의 가로, 세로의 크기를 비교하여 가로 <세로 일 경우
가로, 세로를 바꾸어 가로 > 세로로 바꾸어 주고 가로, 세로의 최댓값을 뽑아 곱해주면 됩니다.

해결방안

function solution(sizes) {    
    // 명함이 가로>세로 되도록 정렬하기
    sizes.map(s => s.sort((a, b) => b - a));

    // 가로, 세로 최댓값 구하기
    let maxW = Math.max.apply(null, sizes.map(s => s[0]));
    let maxH = Math.max.apply(null, sizes.map(s => s[1]));

    return maxW * maxH;
}

해결방안 순서

  1. 명함이 가로>세로 되도록 정렬하기
  2. 가로, 세로 최댓값 구하기

 

1단계. 명함이 가로>세로 되도록 정렬하기

위에서 가로, 세로의 길이를 비교해서 큰 수는 앞으로 작은 수는 뒤로 정렬해야 된다고 했습니다.

이 말은 sort()메서드로 내림차순으로 정렬해야 된다는 것입니다.

그전부터 말했지만 정렬 얘기만 나오면 무조건 sort()를 사용해야 됩니다.

(진짜 sort() 메서드는 정말 중요해요!!!!!)

 

그렇지만 이번 문제는 1차원 배열을 정렬하는 것이 아니라 2차원 배열을 정렬하는 거라

sort() 메서드만 쓰면 안 되고 map()도 사용해야 2차원 배열을 쉽게 정렬할 수 있습니다.

 

MDN Web Docs
sort() 메서드는 배열의 요소를 적절한 위치에 정렬한 후 그 배열을 반환합니다.

구문 : 배열.sort(정렬 순서를 정의하는 함수)

 

sort() 메서드는

  • sort((a,b)=>a-b); -> 오름차순
  • sort((a,b)=>b-a); -> 내림차순

 

MDN Web Docs
map() 메서드는 배열 내의 모든 요소 각각에 대하여 주어진 함수를 호출한 결과를 모아 새로운 배열을 반환합니다.

구문 : arr.map(callback(currentValue[, index[, array]])[, thisArg])

  • callback : 새로운 배열 요소를 생성하는 함수. 다음 세 가지 인수를 가집니다.
  • currentValue : 처리할 현재 요소.
  • index Optional : 처리할 현재 요소의 인덱스.
  • array Optional : map()을 호출한 배열.
  • thisArg Optional : callback을 실행할 때 this로 사용되는 값.
// map()메서드 예제
const array1 = [1, 4, 9, 16];
const map1 = array1.map(x => x * 2);

console.log(map1); // map1 = [2, 8, 18, 32]

 

1단계. 명함이 가로>세로 되도록 정렬하기
sizes.map(s => s.sort((a, b) => b - a));

여기서 테스트 1로 설명하자면

(sizes = [[60, 50], [30, 70], [60, 30], [80, 40]])

s는

  1. [60, 50]
  2. [30, 70]
  3. [60, 30]
  4. [80, 40]

순으로 나오게 되고

 

  1. [60, 50] -> [60, 50]
  2. [30, 70] -> [70, 30]
  3. [60, 30] -> [60, 30]
  4. [80, 40] -> [80, 40]

이런 순으로 배열을 반환하게 됩니다.

테스트 1
sizes = [[60, 50], [30, 70], [60, 30], [80, 40]] -> [[60, 50], [70, 30], [60, 30], [80, 40]]

테스트 2
sizes = [[10, 7], [12, 3], [8, 15], [14, 7], [5, 15]] -> [[10, 7], [12, 3], [15, 8], [14, 7], [15, 5]]

테스트 3
sizes = [[14, 4], [19, 6], [6, 16], [18, 7], [7, 11]] -> [[14, 4], [19, 6], [16, 6], [18, 7], [11, 7]]

 

2단계. 가로, 세로 최댓값 구하기

이제 첫 번째 수에서 가장 큰 수, 두 번째 수에서 가장 큰 수를 뽑아서 그 두 수를 곱해야 되는데요.

최댓값을 구할 때 가장 쉬운 방법은 Math.max.apply()함수를 사용하는 겁니다.

 

MDN Web Docs
Math.max() 함수는 입력값으로 받은 0개 이상의 숫자 중 가장 큰 숫자를 반환합니다.

문법

Math.max()
Math.max(값0)
Math.max(값0, 값1)
Math.max(값0, 값1, ... , 값N)

  • 값1, 값2, ... : 가장 큰 값을 선택하고 반환할 0개 이상의 숫자입니다.
// Math.max.apply()함수 예제
console.log(Math.max(1, 3, 2)); // 3

console.log(Math.max(-1, -3, -2)); // -1

const array1 = [1, 3, 2];
console.log(Math.max(...array1)); // 3

 

 

마지막을 예제를 보시면 Math.max() 함수에는 스프레드 연산자(...배열 : 앞에 ...을 넣는 거를 스프레드 연산자라고 합니다.)를 사용하여 배열을 넣어 배열의 원소의 최댓값을 구할 수 있습니다.

 

마지막 예제처럼 스프레드 연산자를 바로 넣을 수 있으면 좋겠지만

이렇게 하려면 무조건 1차원 배열만 가능합니다.

(Math.max() 함수 안에는 1차원 배열밖에 사용을 못합니다.)

 

그래서 2차원 배열을 1차원으로 바꾸어서 따로 계산을 해야 되는데요.

이 말을 코드로 설명하자면

// 2차원 배열을 1차원 배열로 만들고 최대값을 구하기
let arr1 = sizes.map(s => s[0]);
let arr2 = sizes.map(s => s[1]);

let max1 = Math.max(...arr1);
let max2 = Math.max(...arr2);


// 만약 sizes = [ [ 60, 50 ], [ 70, 30 ], [ 60, 30 ], [ 80, 40 ] ]이면
console.log(arr1); //[ 60, 70, 60, 80 ]
console.log(arr2); //[ 50, 30, 30, 40 ]
console.log(max1); // 80
console.log(max2); // 50

이렇게 됩니다. 

 

물론 이 코드도 좋지만 2줄로 줄일 수 있는 코드를 굳이 4줄로 쓸 필요 없기도 하고 줄일 수 있는 건 줄이는 게 좋잖아요.그래서 사용하는 함수가 Math.max.apply(null, numArray); 입니다.

 

MDN Web Docs
Function.prototype.apply()을 사용하여 숫자 배열에서 최대 요소를 찾습니다.
Math.max(1, 2, 3)와 동일하지만 프로그래밍 방식으로 생성된 모든 크기의 배열에서 getMaxOfArray()를 사용할 수 있습니다.
function getMaxOfArray(numArray) {
  return Math.max.apply(null, numArray);
}

이 예제를 토대로 코드를 짜 보면

 

// 2단계. 가로, 세로 최댓값 구하기
let maxW = Math.max.apply(null, sizes.map(s => s[0]));
let maxH = Math.max.apply(null, sizes.map(s => s[1]));

return maxW * maxH;

 

map()메서드를 활용해서 2차원 배열을 1차원으로 만들어 줍니다.

  • sizes.map(s => s[0]) : 2차원 배열 안에 1차원 배열의 0번째 원소 반환
  • sizes.map(s => s[1]) : 2차원 배열 안에 1차원 배열의 1번째 원소 반환

 

테스트 1
sizes = [[60, 50], [30, 70], [60, 30], [80, 40]] -> [[60, 50], [70, 30], [60, 30], [80, 40]]
sizes.map(s => s[0]) -> [60, 70, 60, 80]
sizes.map(s => s[1]) -> [40, 50, 30, 30, 40]

let maxW = Math.max.apply(null, sizes.map(s => s[0])); // 80
let maxH = Math.max.apply(null, sizes.map(s => s[1])); // 50

return maxW * maxH; // 4000

테스트 2
sizes = [[10, 7], [12, 3], [8, 15], [14, 7], [5, 15]] -> [[10, 7], [12, 3], [15, 8], [14, 7], [15, 5]]
sizes.map(s => s[0]) -> [10, 12, 15, 14, 15]
sizes.map(s => s[1]) -> [7, 3, 8, 7, 5]

let maxW = Math.max.apply(null, sizes.map(s => s[0])); // 15
let maxH = Math.max.apply(null, sizes.map(s => s[1])); // 8

return maxW * maxH; // 120

테스트 3
sizes = [[14, 4], [19, 6], [6, 16], [18, 7], [7, 11]] -> [[14, 4], [19, 6], [16, 6], [18, 7], [11, 7]]
sizes.map(s => s[0]) -> [14, 19, 16, 18, 11]
sizes.map(s => s[1]) -> [4, 6, 6, 7, 7]

let maxW = Math.max.apply(null, sizes.map(s => s[0])); // 19
let maxH = Math.max.apply(null, sizes.map(s => s[1])); // 7

return maxW * maxH; // 133

여기까지 프로그래머스 최소직사각형 해결방안에 대해 설명해보았습니다.

728x90
반응형