[TIL] 99클럽 코테 스터디 3일차 TIL - 이진탐색 : 백준 1072 게임 문제 풀이 with python

Today's keyword : 이진탐색

 

문제설명

특정 수의 심사관이 대기자들을 처리할 수 있는 최소 처리 시간을 찾는 문제입니다. 각 심사관마다 한 사람을 처리하는 데 걸리는 시간이 다릅니다. 

https://school.programmers.co.kr/learn/courses/30/lessons/43238?language=python3

프로그래머스

 

문제풀이

이 문제에서 이진탐색을 위한 조건은 대기자 수를 기준으로 합니다. 주어진 정보가 대기자 수이고, 구해야 하는 값은 모든 대기자 수를 처리하는 시간으로 ' 대기자 수'라는 기준에 맞춰 주어진 mid와 times를 이용해 각 심사관이 처리할 수 있는 대기자 수를 계산합니다. 그리고 대기자 수가 주어진 시간(mid)으로 계산한 처리 인원보다 많으면 주어진 시간을 늘리고 주어진 시간보다 처리 인원이 적으면 최소 시간을 구하기 위해 시간을 줄입니다. 

def solution(n, times):
    start = 1
    end = n * max(times)
    result = 0

    while start <= end:
        mid = (start + end) // 2
        cnt = 0
        
        # 각 심사관이 mid 시간 동안 처리할 수 있는 대기자 수 계산
        for time in times:
            cnt += mid // time
        
        if cnt >= n:  # 대기자 수를 처리할 수 있는 경우
            result = mid  # 현재 시간을 결과로 저장
            end = mid - 1  # 시간을 줄여서 더 최소 시간을 찾기
        else:  # 대기자 수를 처리할 수 없는 경우
            start = mid + 1  # 시간을 늘려서 다시 시도

    return result

입력 

• n : 대기자 수 
• times : 각 심사관이 대기자를 처리하는 데 걸리는 시간의 리스트 
• cnt : 현재 mid 시간동안 처리할 수 있는 대기자 수 
• start : 이진탐색의 시작점으로, 최소 시간은 1로 설정
• end:이진 탐색의 끝점으로, 모든 대기자가 가장 느린 심사관에 의해 처리될 때를 최대 시간으로 설정
• mid : 현재 탐색 중인 총 처리 시간 

풀이 

1. 이진탐색 범위 설정 : start, end 설정 (start = 1, end = n * max(times))
2. 중간값 계산 : (start + end) // 2
3. 각 심사관의 처리 가능 대기자 수 계산 : 반복문 사용 cnt += mid // times[i] 계산 
4. 조건에 따른 범위 조정 : 대기자 수와 심사관의 처리 가능 대기자 수 비교하여 탐색 시간(mid) 조정
5. 조건이 맞을 때까지 반복 : start가 end 보다 작거나 같을 때까지 반복하여 모든 대기자를 처리하는 데 필요한 최소 시간(result) 저장 

 

오늘의 회고 

역시나 이진탐색은 조건 설정이 중요! 주어진 정보와 구해야 할 답에 집중해서 조건식을 잘 만들어야 한다.