[99클럽 코테 스터디 22일차 TIL] 프로그래머스 | 입국심사

22일차 이진탐색 Binary search

Problem 

입국심사

프로그래머스

 

 

Sol

각 심사관이 심사하는 데 걸리는 시간 times가 주어졌을 때 n명의 사람이 입국 심사를 받는데 걸리는 최소 시간을 구하는 문제

 

Binary Search

 

Binary search flow~..~ : target은 15

 

데이터가 정렬된 배열에서 검색 범위를 반으로 줄여가며 target을 탐색하는 알고리즘

 

1. 입력 데이터가 정렬된 상태에서 적용
   • Binary Search의 >>핵심 아이디어<<로, 정렬된 배열 정보를 사용하여 문제 해결 시간을 줄임
2. 분할 정복(Divide and Conquer)
   • 탐색 범위를 절반으로 분할 ➡️ 탐색 속도 빠름
   • 보통 처음 Low과 전체 검색 공간 High의 중간 인덱스 "mid"를 찾아 검색 공간을 이등분
   • mid = low + (high-low)/2
3. 재귀적 또는 반복적 구현
   • target과 mid를 비교하는 것을 반복반복
   • target == mid 라면, 배열에서 해당 위치 반환
   • target < mid 라면, 배열의 작은쪽(왼쪽) 절반에서 검색 계속
   • target > mid 라면, 배열의 큰 쪽(오른쪽) 절반에서 검색 계속

 

• 장점
  • 시간 복잡도 O(log n) : 특히 대규모 배열의 경우 선형 탐색(O(n))보다 빠름
  • 빠른 검색을 위해 설계된 해시 테이블과 같은 특수 데이터 구조와 비교할 때, 더 넓은 범위의 문제 해결 가능
• 한계/단점
  • 배열이 정렬되어야 함
    • 비용면😡 : 정렬 비용 
    • 효율면 😡 : 삽입/삭제가 빈번하게 일어나는 데이터 구조에서는 계속 정렬해야함
  • 이진 탐색은 연속된 메모리 공간을 필요로 함
  • 배열 요소가 비교 가능하여서 순서를 지정할 수 있어야 함

 

🌱 참고

GeeksforGeeks | Binary Search Algorithm - Iterative and Recursive Implementation

Binary Search Algorithm - Iterative and Recursive Implementation - GeeksforGeeks

Wikipedia | Binary search

Binary search - Wikipedia

 

 

해결 방법

👀 시간의 흐름(1분~오래걸리는 심사관이 n명을 심사하는 시간)을 반으로 나누어 가면서 최소 시간을 찾을 때까지 반복합니다. min_time부터 max_time 동안 n명을 모두 심사 가능한가를 판단하고 범위를 조절합니다. 전체 범위를 탐색하는 것 보다 범위를 반으로 쪼개어 비교하는 방식입니다.

입국심사 시간

1. 탐색 범위 설정 : 저절로 정렬
이 시간이면 심사가 끝나나? 부족한가? 를 판단하는데 사용
 - min_time : 최소 1분 이상 소요되기 때문에 1
 - max_time : 가장 느린 심사관이 모두(n명)를 심사할 경우의 시간

2. 이진 탐색
 - mid_time : 중간 시간(min_time + max_time) // 2
 - mid_time 동안 심사관이 몇 명의 사람을 pass할 수 있는지 계산
 - pass_people : pass된 사람 수를 누적

3. 조건따라 탐색 범위 조정 및 반복
 - pass_people이 n보다 크거나 같다면 mid_time 동안 심사를 끝낼 수 있다는 뜻이므로 max_time을 축소
 - 그렇지 않다면 시간이 모자르다고 판단해 min_time 증가

4. 탐색 완료

 

---

✔ Answer

def solution(n, times):
    # start initiate
    min_time = 1
    # worst case
    max_time = max(times) * n
    
    while min_time <= max_time:
        mid_time = (min_time + max_time) // 2
        # possible peple to pass during mid_time
        pass_people = 0
        for cur_time in times:
            pass_people += mid_time // cur_time
        
        if pass_people >= n:
            max_time = mid_time - 1
        else:
            min_time = mid_time + 1
            
    return min_time

---

💬 소감

머리가 아파요. Binary search 문제는 손으로 직접 그려보는게 문제 풀기도 편하고 변수명 정하기도 쉬운 것 같습니다.. 화이팅 나도 입국심사받고싶다.