82. 입국심사 Javascript

https://school.programmers.co.kr/learn/courses/30/lessons/43238

프로그래머스

 

1. 문제에 대한 이해

• 우리가 풀어야 할 문제는 무엇인가?
   - 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 구하라
• 주어진 자료는 무엇인가?
   - n = 입국심사를 기다리는 사람
   - times = 한 사람을 심사하는데 걸리는 시간
• 조건은 무엇인가?
   - 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
   - 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
   - 심사관은 1명 이상 100,000명 이하입니다.

2. 계획

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

1. 입국 심사를 하는데 걸리는 최소시간과 최대시간의 중간 값을 구한다.
   
2. 이진탐색을 하는데 n명 보다 수가 크게 나온다면 
   - 최대값을 중간 값으로 바꾸고 왼쪽으로 이진탐색을 진행하며 조건에 부합한지 (총n명을 검사해야됨) 확인한다.
3. n명 보다 수가 작게 나온다면
    - 최소값의 +1을 중간 값으로 바꾸고 오른쪽으로 이진탐색을 진행하며 조건에 부합한지 확인한다.
4. 이진탐색으로 검색을 하다보면 n명을 검사하는 동시에 걸리는 시간은 최소인 시간을 구할 수 있다.
5. 최소 시간을 리턴한다.

3. 실행

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

const solution = (n, times) => {
  let minTime = 0;
  let maxTime = Math.max(...times) * n;

  while (minTime < maxTime) {
    let midTime = Math.floor((minTime + maxTime) / 2);

    const peopleCount = times.reduce((acc, cur) => {
      return acc + Math.floor(midTime / cur);
    }, 0);

    console.log(minTime, midTime, maxTime, peopleCount);

    if (peopleCount >= n) {
      maxTime = midTime;
    } else {
      minTime = midTime + 1;
    }
  }

  console.log(minTime, maxTime);

  return minTime;
};

test('totalTime', () => {
  // expect(solution(6, [7, 10])).toEqual(28);
  expect(solution(6, [4, 10])).toEqual(20);
});

 

 

완전 이진탐색 문제 그 잡채..
이진탐색을 코드로 어떻게 구현해야할지 감이 잡히지 않았는데 
일일히 써가면서 계산을 먼저 해보니 이진탐색의 흐름이 이해가 갔고 
이를 토대로 풀이 계획을 세워서 코드를 작성할 수 있었다.

코드 작성을 끝내고 테스트 몇개가 통과가 되지 않았는데 
이진탐색을 하는데 n명 보다 수가 크게 나온다면 최대값 -1을 중간 값으로 바꾸고 왼쪽으로 이진탐색을 진행하며 조건에 부합한지 (총n명을 검사해야됨) 확인한다.
이 부분이 문제였다.

최대값을 포함해서 중간값으로 넘겨야지 이를 포함한 최소 시간을 구할 수 있었고 
최소값은 범위에 해당하지 않는다면 쓸 일이 없기 때문에 +1을 해줘도 상관없었다.

내일은 징검다리 문제를 이진탐색을 활용해서 풀어봐야겠다.