JavaScript | Programmers 최소직사각형

문제 설명

명함 지갑을 만드는 회사에서 지갑의 크기를 정하려고 합니다. 다양한 모양과 크기의 명함들을 모두 수납할 수 있으면서, 작아서 들고 다니기 편한 지갑을 만들어야 합니다. 이러한 요건을 만족하는 지갑을 만들기 위해 디자인팀은 모든 명함의 가로 길이와 세로 길이를 조사했습니다.

아래 표는 4가지 명함의 가로 길이와 세로 길이를 나타냅니다.

 

1	60	50
2	30	70
3	60	30
4	80	40

가장 긴 가로 길이와 세로 길이가 각각 80, 70이기 때문에 80(가로) x 70(세로) 크기의 지갑을 만들면 모든 명함들을 수납할 수 있습니다. 하지만 2번 명함을 가로로 눕혀 수납한다면 80(가로) x 50(세로) 크기의 지갑으로 모든 명함들을 수납할 수 있습니다. 이때의 지갑 크기는 4000(=80 x 50)입니다.

모든 명함의 가로 길이와 세로 길이를 나타내는 2차원 배열 sizes가 매개변수로 주어집니다. 모든 명함을 수납할 수 있는 가장 작은 지갑을 만들 때, 지갑의 크기를 return 하도록 solution 함수를 완성해주세요.

 

 

제한사항

• sizes의 길이는 1 이상 10,000 이하입니다.
  • sizes의 원소는 [w, h] 형식입니다.
  • w는 명함의 가로 길이를 나타냅니다.
  • h는 명함의 세로 길이를 나타냅니다.
  • w와 h는 1 이상 1,000 이하인 자연수입니다.

---

 

 

내 답안(잘못된 코드!!!)

function solution(sizes) {
    var maxW=0;
    var maxH=0;
    
    sizes.map(x=>{
        x.sort()
        if(x[0]>maxW) maxW=x[0]
        if(x[1]>maxH) maxH=x[1]
    })
    
    return maxW*maxH;
}

테스트 케이스 반 이상이 에러가 남

 

1. 두 변 중 긴 변을 W, 짧은 변을 H로 가정

2. 비교하는 W 기존 W가 길 경우 maxW 대체. H도 마찬가지

3. 곱함

 

이런식으로 생각했는데 에러가 났다.

 

질문하기 글을 살펴보니 나와 같은 케이스가 많았고, 알고보니 sort의 문제였다!

 

sort 는 ASCII 문자 순서로 정렬되어 문자는 제대로 정렬하지만 숫자는 숫자의 크기대로 나오지 않는다!

 

 

문자 정렬

var fruit = ['orange', 'apple', 'banana'];

/* 일반적인 방법 */
fruit.sort(); // apple, banana, orange

 

숫자 정렬

var score = [4, 11, 2, 10, 3, 1]; 

/* 오류 */
score.sort(); // 1, 10, 11, 2, 3, 4 
              // ASCII 문자 순서로 정렬되어 숫자의 크기대로 나오지 않음

/* 정상 동작 */
score.sort(function(a, b) { // 오름차순
    return a - b;
    // 1, 2, 3, 4, 10, 11
});

score.sort(function(a, b) { // 내림차순
    return b - a;
    // 11, 10, 4, 3, 2, 1
});

 

 

object 정렬

var items = [
  { name: 'Edward', value: 21 },
  { name: 'Sharpe', value: 37 },
  { name: 'And', value: 45 },
  { name: 'The', value: -12 },
  { name: 'Magnetic', value: 13 },
  { name: 'Zeros', value: 37 }
];

// value 기준으로 정렬
items.sort(function (a, b) {
  if (a.value > b.value) {
    return 1;
  }
  if (a.value < b.value) {
    return -1;
  }
  // a must be equal to b
  return 0;
});

// name 기준으로 정렬
items.sort(function(a, b) {
  var nameA = a.name.toUpperCase(); // ignore upper and lowercase
  var nameB = b.name.toUpperCase(); // ignore upper and lowercase
  if (nameA < nameB) {
    return -1;
  }
  if (nameA > nameB) {
    return 1;
  }

  // 이름이 같을 경우
  return 0;
});

 

 

참고 링크

Array.prototype.sort() - JavaScript | MDN