입국심사

[hsskey]

입국심사

📝 제약조건

• 입국심사를 기다리는 사람: 1명 이상 1,000,000,000명 이하
• 각 심사관의 심사 시간: 1분 이상 1,000,000,000분 이하
• 심사관 수: 1명 이상 100,000명 이하

💡 예시

• Input: n = 6, times = [7, 10]
• Output: 28

문제 해결 과정

Step 1: 문제 이해하기

• 작은 예시로 직접 풀어보기:
  1. n=2, times=[7] 인 경우
     • 1명의 심사관이 2명을 심사
     • 7분 + 7분 = 14분 소요
  2. n=3, times=[7,10] 인 경우
     • 0분: 각 심사대에 1명씩 배정 (2명)
     • 7분: 7분 심사대가 비어서 1명 더 배정
     • 총 14분 소요

Step 2: 접근 방법

• 이진 탐색으로 접근

  1. 최소 시간(left): 1
  2. 최대 시간(right): 가장 긴 심사시간 × n
  3. 중간 시간(mid)일 때 처리 가능한 사람 수 계산
  4. 처리 가능한 사람 수 vs n 비교하여 범위 좁히기

• 알고리즘 표

  left = 1, right = Math.max(...times) * n
  ↓
  mid = (start + end) / 2
  ↓ 
  mid분 동안 처리할 수 있는 사람 수 계산
  ↓
  처리 가능 인원 >= n -> end = mid
  처리 가능 인원 < n -> start = mid + 1
  ↓
  start와 end가 같아질 때까지 반복

Step 3: 코드 설계

1. 최소/최대 시간 설정
2. 이진 탐색으로 시간 탐색
3. 주어진 시간에 처리 가능한 인원 계산하는 함수 구현
4. 결과값 도출

Step 4: 코드 구현

function solution(n, times) {
    // 최소 시간과 최대 시간 설정
    let start = 1;
    let end = Math.max(...times) * n;

    // 주어진 시간(mid)동안 처리할 수 있는 입국자 수 계산 함수
    const getPossibleCount = (mid) => {
        return times.reduce((acc, time) => acc + Math.floor(mid / time), 0);
    };

    // 이진 탐색
    while (start < end) {
        const mid = Math.floor((start + end) / 2);
        const possibleCount = getPossibleCount(mid);

        // 처리할 수 있는 인원이 n보다 크거나 같으면 시간을 줄여본다
        if(possibleCount >= n) {
            end = mid;
        } else {
        // 처리할 수 있는 인원이 n보다 작으면 시간을 늘린다
            start = mid + 1    
        }
    }

    return start;
}

// 테스트
console.log(solution(6, [7, 10])); // 28

[hsskey]

[hsskey]

[hsskey]