99클럽 코테 스터디 3일차 TIL / 이분 탐색

✏️ 문제

https://school.programmers.co.kr/learn/courses/30/lessons/43238

 

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

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

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

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

 

제한사항

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

 

🤖 입출력 예시

 

🧐 난이도/소요 시간

✅ 난이도: 프로그래머스 Level 3

✅ 소요 시간: 1시간 47분

✅ 권장 시간: 1시간

 

모든 문제를 권장 시간 안에 좀 풀어보고 싶다. 너무 격하게.

 

💡 풀이

1) 문제 유형 파악

 

프로그래머스에서는 문제 유형을 바로 보여주기 때문에 오늘은 유형 파악 시간을 따로 갖지는 않았다.

 

스터디 1일차/2일차에 푼 문제랑 유형(입력 범위 매우 큼, 최솟값 또는 최댓값 구하기)이 완전히 동일하다. 이제 이분 탐색으로 풀 수 있는 유형이 뭔지 보이는 것 같긴 한데 구현하는 건 아직도 조금 어려워서 더 많이 풀어봐야겠다.

 

2) 아이디어 흐름

이전에 푼 2개의 문제에서는 아이디어 흐름을 정리할 때 그냥 핵심 1, 2로 표기했는데, 챗지피티의 도움을 조금 받아서 좋은 표현을 가져왔다.

 

① ⭐핵심 (1) - 범위 설정⭐

end 변수의 초기값에 대해 고민해볼 필요가 있다. 제한 사항에서 주어진 최댓값을 써도 상관없을 것 같지만 조금이나마 탐색 범위를 줄이기 위한 과정이다.

 

입국심사가 가장 오래 걸리는 경우는 심사 시간이 가장 긴 심사관이 n명을 모두 처리하는 것이다. 문제에서 주어진 조건을 이용해 표현하면 n*max(times)라고 할 수 있고 이 값으로 end 변수를 초기화해줬다.

 

이 과정에서 mid 값의 의미도 정의되는데 mid 값은 모든 사람이 심사를 받을 수 있는 임의의 시간을 뜻한다.

 

② ⭐핵심 (2) - 이분 탐색 대상 설정⭐

내가 아직 이분 탐색 문제를 어려워하는 이유는 이 부분 때문이다. 아래는 1일차/2일차 문제에서 사용한 이분 탐색 대상이다.

 

1️⃣ BOJ 게임: 승률(이 때의 mid 값은 추가로 진행하는 게임 횟수를 의미)

2️⃣ BOJ 징검다리: 점프 거리 누적 합(이 때의 mid 값은 K번째 징검다리에서의 점프 거리를 의미)

 

이번엔 이 파트 내용이 좀 길어질 것 같아서 내용을 좀 더 세분화해보겠다.

 

Step. 1

먼저 어떻게든 두 문제 유형에 끼워 맞춰서 탐색 대상을 찾아보려고 했다. 게임 문제는 승률을 이용해야 한다는 게 명확하게 보였기 때문에 패스하고 징검다리 문제에서 쓴 누적 합 개념을 사용할 수 있을 것 같았다.

 

Step. 2

누적 합을 사용하기로 했으면 어떤 값에 이 개념을 적용할지 구체화해야 한다. 사실 처리 인원 수 말고 다른 값이 떠오르지 않아서 이 값을 사용했는데 운이 좋게 방향이 잘 맞았던 것 같다.

 

처리 인원 수는 mid를 times 안에 있는 값(time으로 표현)으로 나눈 몫을 더해주면서 늘려가면 된다. mid를 저 값으로 나누는 이유는 mid//time이 해당 심사관이 최대로 처리할 수 있는 인원이기 때문이다.

 

누적 처리 인원이 n보다 클 경우: 임의의 시간 mid 안에 모든 인원을 처리할 수 있다는 뜻이다. 문제에서 요구한 사항은 '최솟값'이기 때문에 end = mid-1로 줄여 가장 작은 값을 찾아나가면 된다.

 

누적 처리 인원이 n보다 작을 경우:  모든 인원을 처리하기에는 시간이 부족하다는 의미이기 때문에 start = mid+1로 늘려 값을 증가시킨다.

 

3) 구현

def solution(n, times):
    answer = float("inf")
    
    times.sort()
    
    start, end = 1, n*max(times)

    while start <= end:
        mid = (start+end)//2
        
        done = 0

        for time in times:
            done += mid//time
        
        if done >= n:
            answer = min(mid, answer)
            
            end = mid-1
        else:
            start = mid+1
        
    return answer

 

4) 어려웠던 점/배운 점

🚨 어려웠던 점

• 점프 거리 누적 합이 N보다 클 때, 작을 때의 의미를 파악하는 데에 시간이 조금 걸렸다.

❗ 배운 점

• 이분 탐색 유형 문제를 풀 때는 범위 설정 → 이분 탐색 대상 설정 → 탐색 조건 검사 이 세 단계를 기억해두고 사용하면 좋다는 것을 배울 수 있었다.
• 이 문제는 처음에 정렬 없이 제출했는데 통과가 됐지만 이분 탐색 유형을 풀게 되면 항상 정렬하고 시작하는 습관을 가져야겠다.