[CodeKata] 프로그래머스 : 5.12(수), 입국심사

🥋 Oooth More!! (Level 3)

* 출처링크 : hsin.hr/coci/archive/2012_2013/contest3_tasks.pdf

 

🧮 풀이

* 6, 9번에서 실패가 발생하였다.

function solution(n, times) {
  let min = 0;
  let max = n * Math.min.apply(null, times);
  
  while (max - min >= 0) {
    const mid = Math.floor((max - min) / 2) + min;
    const totalTime = times.reduce((acc, cur) => acc + Math.floor(mid/cur), 0);
    
    if (totalTime < n) {
      min = mid + 1;
    }
    else if (totalTime > n) {
      max = mid - 1;
    }
    else {
      if (times.some(time => mid % time === 0)) {
        return mid;
      }
      else {
        // n(검사인원)은 맞는데 times 숫자들의 배수가 아닌 예외 처리
        let count = 1;
        while (true) {
          if (times.some(time => (mid+count) % time === 0)) return mid+count
          else if (times.some(time => (mid-count) % time === 0)) return mid-count
          else count++;
        }
      }
    }
  }
}

1. 이진탐색(Binary Search) 구현을 위해 min과 max를 설정한다. max는 검사시간이 가장 빠른 사람이 모든 사람을 검사하는 경우.
2. max가 min과 만날때까지 while 반복문을 실행하며 이진탐색을 실행한다. mid는 min, max의 중간값이다.
3. totalTime은 현재시간값(mid) 동안 모든 검사원이 검사할 수 있는 사람수의 합이다. reduce()로 누적하며, mid/cur를 floor 처리.
4. 이 totalTime이 n보다 작으면 mid가 높아져야 하므로 min값을 올린다. 반대의 경우엔 max값을 내려서 최소값을 찾는다.
5. 이외의 경우엔, mid 시간에 n명을 검사하게 된다. 여기서, mid가 times의 어떤 시간값의 배수인 경우 정답이므로 mid를 반환한다.
6. 만약, times 시간값의 배수가 아니라면 n명을 검사할 수 있는 시간은 맞으나, 검사원의 시간값 배수가 아니므로 이를 찾아야 한다.

마지막 6번에서 예외처리를못하고 2개의 케이스에서 오류가 발생했다. 배열 인덱싱이 아닌 값의 이진탐색이다 보니 고려할 게 많았다.

모범답안을 통해, 부족했던 부분을 보완함과 동시에 이진탐색을 좀 더 확실하게 학습하고 넘어가야겠다.

 

🖇 리뷰

function solution(n, times) {
    times.sort((a,b) => a-b); 
    let left = 1;
    let right = n * times[times.length -1];
    let answer = right; // 최대값.
    while(left <= right){
        let mid = Math.floor((left + right) / 2);
        let count = 0
        times.forEach(value => {
            count += Math.floor(mid / value); // 한 사람당 몇명 할 수 있는지
            if(count >= n) {
                answer = Math.min(mid, answer); // 최솟값
                return;
            };
        });
        if (count >= n) { 
            right = mid - 1;
        }
        else {
            left = mid + 1;
        }
    }
    return answer;
}

* 출처 : velog.io/@ansrjsdn/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-level3-%EC%9E%85%EA%B5%AD%EC%8B%AC%EC%82%AC

• 우선, right 값을 가장 오래 걸리는 사람이 모든 인원을 검사하는 경우로 설정했다. (극한의 경우)
• 또한, answer 정답값 변수를 별도로 관리했다. 여기에 최소값을 누적할 것이므로, 우선 최대값인 right를 넣었다.
• mid값을 아주 심플하게 구할 수 있다. 그냥 (left + right) 평균값을 Math.floor() 처리해주면 되었다!
• count는 내 totalTime과 같다. 이 count가 n 이상이 되면 적합한 경우이다. 이 때, 현재 answer과 mid의 최소값으로 최신화한다.
• 또한, count가 n보다 작은 경우엔 left를 올려주고, count가 n 이상인 경우엔 right를 내려서 최소값을 계속해서 탐색한다.