106. 이것이 코딩 테스트다 8장 : 효율적인 화폐 구성 Javascript

1. 문제에 대한 이해

• 우리가 풀어야 할 문제는 무엇인가?
   - M원을 만들기 위한 최소한의 화폐 개수를 구하라
• 주어진 자료는 무엇인가?
   - N = 화폐 종류
   - M = 정수
• 조건은 무엇인가?
   - 최소한의 화폐 개수를 출력하지 못할 경우 -1을 리턴한다.

2. 계획

1. 가장 큰 단위의 화폐를 M으로 나눈다.
2. 나누어 떨어진다면 그 값을 리턴
3. 나누어 떨어지지 않는다면 M에서 두번째로 큰 단위의 화폐를 빼고 1번 반복
4. 화폐 단위 어떤것으로도 M이 나누어 떨어지지 않는다면 -1 리턴한다.

3. 실행

• 풀이 계획을 실행하고, 각 단계가 올바른지 점검하라.

const solution = (N, M, count = 0) => {
  // 가장 큰 단위의 화폐를 M으로 나눈다.
  const sortN = N.sort((a, b) => b - a);

  // 나누어 떨어진다면 그 값을 리턴
  if (M % sortN[0] === 0) {
    return count + M / sortN[0]
  }

  // 화폐 단위 어떤것으로도 M이 나누어 떨어지지 않는다면 - 1 리턴한다.
  for (i = 0; i < N.length; i++) {
    if (M % N[i] !== 0) {
      return -1
    }
  }

  // 나누어 떨어지지 않는다면 M에서 두번째로 큰 단위의 화폐를 빼고 count+1 하고 1번 반복
  return solution(N, M - sortN[1], count + 1)
};

test('countMoney', () => {
  expect(solution([2, 3], 15)).toEqual(5);
  expect(solution([3, 5, 7], 4)).toEqual(-1);
});

4. 반성

• 다이나믹 프로그래밍을 사용하라는 문제 해설과는 다르게 풀었는데 테스트 케이스는 전부 통과를 하지만 다른 예외 케이스들이 통과를 할 지 의문이다.
• 큰 단위의 화폐부터 처리하는 방법으로 해결할 수 없다고 하는데 큰 단위 화폐 부터 처리하는 방식으로 문제를 풀었기 때문에 허점이 있을것이라는 생각이 들었고 다른 방법을 찾아봐야겠다.