[프로그래머스][LV.3] 입국심사 | python3

문제링크:  입국심사

---

문제설명

n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.

처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.

모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.

입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.

 

제한조건

- 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
- 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
- 심사관은 1명 이상 100,000명 이하입니다.

 

---

 

문제풀이

def solution(n, times):
    answer = 0
    chk=[-1,-1] # 심사대
    
    temp1=0 # 심사대 1이 비기까지 남은 시간
    temp2=0 # 심사대 2가 비기가지 남은 시간
    real_time=0
    for i in ragne(n):
        # 두 심사대가 비었을때
        # 리스트 안의 원소로 비교하는 것보다 temp로 비교하는게 나을수도
        if temp1==temp2==0: 
            chk[0]=i
            temp1=7
            answer+=7
            
        elif chk[0]==
    return answer

 

이런식으로 접근하는 게 아닌 것 같다. 루프문 돌리기가 애매함...

 

이분탐색으로 푸는 문제.

 

✔ 이분 탐색 조건: "정답이 특정 범위 안에 존재하며, 단조 증가/감소하는 성질이 있는가?"

이 문제를 풀기 위해서는 최소한의 시간(T)을 찾아야 함.
그리고, 특정 T 시간이 주어졌을 때:

1. T 시간 안에 n명을 심사할 수 있으면, T보다 작은 최적의 해가 있는지 확인해야 함 → 더 작은 T를 탐색
2. T 시간 안에 n명을 심사할 수 없다면, 시간이 부족하므로 더 큰 T를 탐색

즉, T를 기준으로 "가능 여부"를 판단하며 탐색 범위를 절반씩 줄여나갈 수 있음!
➡ 이분 탐색의 전형적인 패턴

 

이분 탐색 (Binary Search)

1. 이분 탐색이란?

이분 탐색(Binary Search)은 정렬된 데이터에서 특정 값을 빠르게 찾는 알고리즘이다. 검색 범위를 절반씩 줄여나가기 때문에 매우 효율적이다.

2. 이분 탐색의 동작 원리

1. 정렬된 배열에서 탐색을 수행한다.
2. 탐색 범위의 가운데 값(mid)을 선택한다.
3. mid 값이 찾고자 하는 값과 같다면 탐색 종료.
4. mid 값이 찾는 값보다 크다면 왼쪽 절반에서 탐색을 계속한다.
5. mid 값이 찾는 값보다 작다면 오른쪽 절반에서 탐색을 계속한다.
6. 이를 반복하여 탐색 범위를 줄여나가며 값을 찾는다.

3. 이분 탐색의 시간 복잡도

• 이분 탐색은 탐색 범위를 절반씩 줄여나가기 때문에 O(log N) 의 시간 복잡도를 가진다.
• 예를 들어, 데이터 개수가 1,000,000(백만) 개라면, 최악의 경우에도 약 20번만 탐색하면 된다.

4. 이분 탐색의 구현 방법

4.1. 반복문을 이용한 이분 탐색 (Iterative Binary Search)

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        
        if arr[mid] == target:
            return mid  # 찾은 경우 인덱스 반환
        elif arr[mid] < target:
            left = mid + 1  # 오른쪽 절반 탐색
        else:
            right = mid - 1  # 왼쪽 절반 탐색
    
    return -1  # 찾지 못한 경우

4.2. 재귀를 이용한 이분 탐색 (Recursive Binary Search)

def binary_search_recursive(arr, target, left, right):
    if left > right:
        return -1  # 탐색 실패
    
    mid = (left + right) // 2
    
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        return binary_search_recursive(arr, target, left, mid - 1)

5. 이분 탐색이 유용한 경우

• 데이터가 정렬되어 있을 때 빠르게 탐색할 수 있다.
• 탐색 범위가 매우 클 때 (ex. 10^9 이상) 효율적인 탐색이 필요할 경우.
• 최적화 문제 해결 (ex. 특정 조건을 만족하는 최적의 값 찾기)

6. 이분 탐색을 활용한 문제 예시

6.1. 정렬된 배열에서 특정 값 찾기

• 예: arr = [1, 3, 5, 7, 9]에서 target = 5를 찾기.

6.2. Lower Bound & Upper Bound

• Lower Bound: target 이상의 첫 번째 원소의 위치 찾기.
• Upper Bound: target 초과하는 첫 번째 원소의 위치 찾기.

6.3. 파라메트릭 서치 (Parametric Search)

• 특정 조건을 만족하는 최댓값 / 최솟값을 찾는 문제.
• 예: 입국 심사 문제, 공유기 설치 문제 등.

정리

✅ 이분 탐색은 정렬된 배열에서 빠르게 값을 찾는 방법이다.
✅ 탐색 범위를 절반씩 줄이므로 O(log N)의 시간 복잡도를 가진다.
✅ 최적화 문제 해결에도 자주 사용된다.

가장 적게 걸릴 시간부터 가장 오래 걸릴 시간까지를 범위로 잡는다.

(mid) 중간 지점을 찾아 그 시간동안에는 몇명의 사람이 심사받을 수 있는지 계산한다.

n보다 많으면 더 적은 시간쪽으로 가서 반복

n보다 적으면 더 많은 시간쪽으로 가서 반복

나의코드

def solution(n, times):
    answer = 0
    left,right=1,max(times)*n
    
    # 이분탐색을 하기 위한 left와 right
    while left<=right:
        mid=(left+right)//2 # 이분탐색
        people = 0
        for time in times: # 주어진 시간동안 동시에 심사대가 심사할 수 있기때문에
            people += mid//time
            
            if people>=n: # 조기종료(for문)
                right=mid-1
                answer=mid
                break
        
        if people<n:
            
            left=mid+1
        # else:
        #     answer=mid
        #     right=mid-1
    return answer

 

---

 

참고하기