💻 이진 탐색 by 프로그래머스 연습문제

트리의 개념과 순회, 힙, 트라이, 정렬, 이진 탐색에 대해서 배웠다. 정렬 문제 가장 큰 수 에서도 1시간동안 테스트케이스 실패를 해결하기 위해 보냈다. 그럼에도 정렬 문제 보다는 알고리즘이 익숙하지 않은 입국 심사 문제를 회고하고 싶어서 적는다.

📍 이진 탐색

입국 심사

출처 : 프로그래머스
입국 심사

내 답안

function solution(n, times) {
  times.sort((a, b) => a - b);

  let minTime = 0;
  let left = 1;
  let right = n * Math.max(...times);

  while (left <= right) {
    let midTime = Math.floor((left + right) / 2);
    let peopleCnt = 0;

    for (const time of times) {
      peopleCnt += Math.floor(midTime / time);
    }

    if (peopleCnt >= n) {
      minTime = midTime;
      right = midTime - 1;
    } else {
      left = midTime + 1;
    }
  }
  return minTime;
}

💡구현 방법

어제 알고리즘 특강에서 제한사항을 보면 대충 어떤 알고리즘으로 짜야할 지 보인다고 하였다.
그래서 제한사항에 1,000,000,000 이가 때문에 이 문제는 무조건 이진 탐색으로 푸는 것이라 확신을 했고 구현해보았다.

1. 우선 이진 탐색은 데이터들이 정렬 되어 있어야 사용할 수 있기 때문에 먼저 times를 정렬하였다.
2. 최소, 최대 시간를 구한 뒤 구하려는 답을 이진 탐색으로 범위를 좁혀 가며 답을 구한다.
   • 최소, 최대 시간의 중간값인 midTime가 n명을 심사 할 수 있는지 아닌지를 파악하였다.
3. n명을 심사 할 수 있다면 minTime을 갱신하고 최대 범위를 줄이고 n 명을 심사할 수 없다면 최소 시간을 늘려주도록 반복하였다.

모범 답안

function solution2(n, times) {
  const sortedTimes = times.sort((a, b) => a - b);
  let left = 1;
  let right = sortedTimes[sortedTimes.length - 1] * n;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    const sum = times.reduce((acc, time) => acc + Math.floor(mid / time), 0);

    if (sum < n) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return left;
}

🔥 느낀점

문제 제한조건을 보고 유형 찾기❗️
어제 알고리즘 특강에서 문제 유형 파악 방법에서 아래와 같은 부분을 얘기해주셨다.

1. 문제 유형을 바로 파악하는 것보다는 가능성 있는 방법을 좁혀나가라
2. 입출력 제한부터 확인

그래서 오늘 문제를 볼 때 1,000,000,000 라는 제한과 ~라는 조건을 만족하는 최대/최소 값을 찾아라을 보자마자 바로 이진 탐색이 떠올랐고 "아 이렇게 연상되니까 바로 풀 수 있겠구나" 라고 생각하게 되었다.😊

또한 저는 minTime을 선언 하여 중간에 갱신해주었는데 left와 right만으로도 계산할 수 있다는 것을 알았다. return값을 left로 하면 되는 거였는데.. 이게 알고리즘을 완벽히 이해하지 못해서 생긴 변수가 아닐까 싶었다.😱
몇 일 동안 알고리즘을 풀고 있는데 다 알고있는 알고리즘임에도 불구하고 허점도 많고 허술하게 익혔다는 생각이 계속 들었다. 앞으로 지금처럼 꾸준히 노력해야지🤯

Refer

코딩테스트 연습 | 프로그래머스

오늘의 내용 정리

데브코스 Day5