[프로그래머스] 입국심사 - Level 3 (Python)

📌 문제 정보

입국심사 Level 3

플랫폼

프로그래머스

유형

이진탐색, 매개변수 탐색

언어

Python 3

풀이 시간

약 70분

풀이 날짜

2026.06.05

문제 링크

바로가기 ↗

---

🧩 문제 요약

n명의 사람이 입국심사를 기다리고 있고, 각 심사관마다 한 명을 심사하는 데 걸리는 시간이 다를 때, 모든 사람이 심사를 마치는 데 걸리는 최소 시간을 구하는 문제

입력 조건:

• n: 심사를 기다리는 사람 수
• times: 각 심사관이 한 명을 심사하는 데 걸리는 시간 배열

출력 조건:

• n명 모두가 심사를 받기까지 걸리는 최소 시간 반환

---

💡 나의 접근 방식

1단계 - 처음 든 아이디어

"최소 시간을 구하라"는 말에 처음엔 그리디하게 접근했다. 매 순간 가장 빨리 비는 심사관에게 다음 사람을 배정하는 시뮬레이션을 떠올렸지만, n과 times의 원소 값이 최대 10억까지 갈 수 있어서 시뮬레이션으로는 시간 초과가 날 게 뻔했다.

2단계 - 막혔던 부분

"시간"이라는 답을 직접 구해야 하는데, 정렬된 배열도 아니고 탐색할 대상 자체가 명확하지 않아서 한동안 감을 잡지 못했다. "이진탐색은 정렬된 배열에서 값을 찾는 것"이라는 고정관념 때문에 이 문제에 이진탐색을 적용할 수 있다는 게 잘 연결되지 않았다.

3단계 - 해결 실마리

이진탐색은 꼭 배열이 아니어도, 단조성이 있는 모든 범위에 적용할 수 있다는 걸 깨달았다.

• 시간이 늘어날수록 심사 가능한 인원도 늘어나는 단조증가 관계가 성립
• mid라는 특정 시간을 기준으로 "이 시간 안에 n명을 심사할 수 있는가?"를 판단하는 함수만 만들면 이진탐색 적용 가능
• 이런 형태를 매개변수 탐색(Parametric Search) 이라 부르며, 값을 찾는 게 아니라 "조건을 만족하는 최솟값/최댓값"을 찾을 때 쓰인다

핵심 아이디어:

• 탐색 범위: left = 1(또는 가장 빠른 심사관 시간), right = max(times) * n(최악의 경우 가장 느린 심사관 혼자 다 처리)
• mid 시간이 주어졌을 때, 각 심사관이 처리 가능한 인원(mid // t)을 모두 더해서 n명 이상이면 시간을 줄이고, 부족하면 시간을 늘림
• 가능한 값은 절대 버리지 않고 불가능한 값만 제거하는 방식으로 탐색 범위를 좁혀가면 마지막에 남는 값이 곧 정답

---

✅ 최종 풀이 코드

def solution(n, times):
    answer = 0

    left = min(times)
    right = max(times) * n

    while left != right:
        mid = (left + right) // 2
        count = 0
        for t in times:
            count += mid // t

        if count >= n:
            right = mid
            answer = mid
        else:
            left = mid + 1

    return answer

---

📊 복잡도 분석

구분 복잡도 근거

시간 복잡도	O(M log(max(times) × n))	이진탐색으로 탐색 범위를 절반씩 줄이며(log(범위)), 매 회차마다 모든 심사관(M명)을 순회하며 가능 인원을 계산
공간 복잡도	O(1)	추가 배열 없이 변수만 사용

탐색 범위가 최대 10억 × 10억까지 갈 수 있는 큰 값이라 단순 시뮬레이션이나 완전탐색으로는 절대 시간 안에 풀 수 없다. 이진탐색 덕분에 범위가 아무리 커도 log 수준으로 빠르게 줄어든다.

---

❌ 오답 노트

시도 틀린 이유 수정 내용

1차	매 순간 가장 빨리 비는 심사관에게 배정하는 시뮬레이션 방식 시도 → n과 times 값이 최대 10억까지 가능해서 시간 초과 발생	시뮬레이션 대신 "정답이 될 수 있는 시간 범위"를 이진탐색으로 좁혀나가는 방식으로 전환
2차	이진탐색이 정렬된 배열에서만 쓰인다고 생각해서 적용 방법을 떠올리지 못함	단조성(시간이 늘수록 심사 가능 인원도 늘어남)만 있으면 배열이 아니어도 이진탐색 적용 가능하다는 점을 이해
3차	통과 ✅	-

---

🔄 다른 풀이 방법

low <= high 조건 + mid - 1로 범위 좁히기

def solution(n, times):
    answer = 0
    low = 1
    high = max(times) * n

    while low <= high:
        mid = (low + high) // 2
        count = 0

        for t in times:
            count += mid // t

        if count >= n:
            answer = mid
            high = mid - 1
        else:
            low = mid + 1
    return answer

left != right vs low <= high 비교:

• left != right 방식: 가능한 값을 만나면 right = mid로 mid 자체를 포함시켜 범위를 좁히고, 종료 시점에 left(또는 right)가 곧 정답. 정답을 별도 변수에 저장하지 않아도 됨.
• low <= high 방식: 가능한 값을 만날 때마다 answer에 정답 후보를 저장해두고, high = mid - 1로 mid를 범위에서 완전히 제외. 루프가 끝났을 때 answer에 최종 정답이 남아있음.
• 두 방식 모두 "가능한 값은 버리지 않고, 불가능한 값만 제거한다"는 핵심 원리는 동일하다. 다만 **정답을 어디서 기록하느냐(answer 변수 vs 수렴한 포인터)**에 따라 종료 조건과 범위를 좁히는 디테일이 달라진다.

---

📝 배운 점 & 회고

• ✏️ 새로 알게 된 것: 이진탐색은 정렬된 배열뿐 아니라 단조성이 있는 모든 범위에 적용할 수 있다. "mid를 기준으로 가능/불가능을 판단할 수 있는가"가 이진탐색 적용 여부를 가르는 기준이다.
• ✏️ 새로 알게 된 것: 값을 직접 찾는 일반적인 이진탐색과 달리, 조건을 만족하는 최솟값/최댓값을 찾는 형태는 매개변수 탐색(Parametric Search) 이라는 별도 용어로 불린다.
• ✏️ 새로 알게 된 것: "범위가 너무 커서 완전탐색이 불가능하고, 구하려는 게 최솟값/최댓값이며, mid에 대해 가능/불가능 판단이 가능하다"는 세 조건이 맞아떨어지면 이진탐색을 의심해봐야 한다.
• ⚠️ 실수했던 점: 처음엔 시뮬레이션으로 접근했다가 시간 복잡도를 너무 늦게 고려했다. 입력값의 최댓값(10억)을 먼저 확인했다면 더 빨리 이진탐색을 떠올렸을 것 같다.
• 💬 한 줄 요약: 배열이 없어도 단조성만 있으면 이진탐색이다. mid로 가능/불가능을 판단할 수 있는지부터 확인하자!