[알고리즘] 프로그래머스의 "예산" 문제를 Javascript로 풀으며

오늘 필자는 자바스크립트로 프로그래머스의 예산 문제를 풀었었습니다.

 

몇일 전에 파이썬으로 풀었던 코드를 바탕으로 테스트 케이스를 먼저 만들고 알고리즘을 만들며 풀어나갔는데 테스트 케이스 5번, 7~16번이 틀렸습니다. 이상했었습니다. 파이썬 코드에서는 같은 코드가 정답이라고 나와있었기 때문입니다.

 

function solution(d, budget) {
  let count = 0;
  let acc = 0;
  d.sort();

  for (const val of d) {
    if (acc + val > budget) {
      break;
    }

    acc += val;
    count += 1;
  }


  return count;
}

의심되는 테스트 케이스를 만들고 반복적으로 풀었습니다. 계속 틀렸었습니다. 마지막으로 MDN의 javascript sort()를 확인했었는데 이 메서드 에서는 “compare 함수가 제공되지 않으면 각 문자의 유니코드 포인트 값에 따라 정렬됩니다”고 나와있었습니다.

 

 

필자는 “아차!”와 함께 테스트 케이스 d = [1, 2, 10, 30], budget = 10, 기대 값 2를 넣어 코드를 실행 했었습니다. 아니나 다를까, 실행한 결과 값에서는 1으로 나왔었습니다. 정렬된 d [1, 2, 10, 30]가 [1, 10, 2, 30]로 되었기 때문입니다.

 

 

필자는 sort() 를 sort((a,b) => a -b)로 고치고 다시 실행했더니 모두 통과 되었습니다.

function solution(d, budget) {
  let count = 0;
  let acc = 0;
  d.sort((a, b) => a - b);

  for (const val of d) {
    if (acc + val > budget) {
      break;
    }

    acc += val;
    count += 1;
  }


  return count;
}

 

배운점들

• sort()는 기본으로 각 문자의 유니코드 포인트 값에 따라 정렬됩니다.
• sort()는 숫자대로 정렬할때 compare 함수를 꼭 제공해야 합니다.