102. 이것이 코딩 테스트다 7장 : 떡볶이 떡 만들기 Javascript

1. 문제에 대한 이해

• 우리가 풀어야 할 문제는 무엇인가?
   - 손님이 요청한 총 길이가 M일 때 적어도 M 만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하라
• 주어진 자료는 무엇인가?
   - N = 떡의 개수
   - M = 요청한 떡의 길이
   - arr = 떡의 개별 높이

2. 계획

• 이 문제를 푸는데 있어서 유용하게 쓸 수 있는 지식은 무엇인가?
   - 이진탐색

1. start값을 0, end 값을 arr의 가장 큰 값, mid 를 start와 mid의 중간값으로 둔다.
2. arr에서 mid를 뺀 다음에 다 더한 값이 M이면 이때의 mid 값을 리턴한다.
3. arr에서 mid를 뺀 다음에 다 더한 값이 M보다 작으면 end를 mid-1로 바꾸고 mid값은 새로 계산된다.
4. arr에서 mid를 뺀 다음에 다 더한 값이 M보다 크면 start를 mid+1로 바꾸고 mid값은 새로 계산된다.

3. 실행

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

const solution = (M, arr, start = 0, end = Math.max(...arr)) => {
  // start값을 0, end 값을 arr의 가장 큰 값, mid 를 start와 mid의 중간값으로 둔다.
  let mid = Math.floor((start + end) / 2);

  // mid 보다 긴 떡만 잘라야한다.
  let newArr = arr.filter((it) => it > mid);

  //arr에서 mid를 뺀 다음에 다 더한 값을 구한다.
  let sumLength = newArr.reduce((acc, cur) => acc + (cur - mid), 0);

  // arr에서 mid를 뺀 다음에 다 더한 값이 M이면 이때의 mid 값을 리턴한다.
  if (sumLength === M || start > end) {
    return mid;
  }

  // arr에서 mid를 뺀 다음에 다 더한 값이 M보다 작으면 end를 mid - 1로 바꾸고 mid값은 새로 계산된다.
  if (sumLength < M) {
    return solution(M, arr, start, end = mid - 1)
  }

  // arr에서 mid를 뺀 다음에 다 더한 값이 M보다 크면 start를 mid + 1로 바꾸고 mid값은 새로 계산된다.
  if (sumLength > M) {
    return solution(M, arr, start = mid + 1, end)
  }
};

test('findHeight', () => {
  expect(solution(6, [19, 15, 10, 17])).toEqual(15);
  expect(solution(7, [19, 15, 10, 17])).toEqual(14);
  expect(solution(13, [19, 15, 10, 17])).toEqual(12);
  expect(solution(14, [19, 15, 10, 17])).toEqual(12);
  expect(solution(15, [19, 15, 10, 17])).toEqual(12);
});