[프로그래머스] 입국심사

문제

프로그래머스 입국심사

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

프로그래머스

 

코드

def solution(n, times):
    answer = 0
    # s(start), e(end) 투포인터!
    s = 1
    e = max(times) * n

    while s <= e:   # 교차될때 스탑
        mid = (s+e) // 2
        check_person = 0
        for time in times:
            check_person += mid // time  # check_person 은 모든 심사관들이 mid분 동안 심사한 사람의 수
            if check_person >= n:
                break

        #업?
        if check_person >= n:
            e = mid - 1
            answer = mid
        # 다운?
        else:
            s = mid + 1

    return answer

 

풀이

s = 1
e = max(times) * n

시작점과 끝점은 이분탐색 할곳의 범위다.

투포인터로 시작점과 끝점을 지정해준다.

 

모든 사람이 심사받는데 걸릴 수 있는 시간을 범위로 잡을것이기 때문에

시작점은 1,

끝점은 (최대 입국심사 기간) * (대기인원) 으로 설정한다.

 

while s <= e:   # 교차될때 스탑
    mid = (s+e) // 2
    check_person = 0
    for time in times:
        check_person += mid // time  # check_person은 모든 심사관들이 mid분 동안 심사한 사람의 수
        if check_person >= n:
            break

mid는 범위내 중간지점이다.

s ~ e 범위 내에서 check_person이 n이 되는 순간을 찾는다.

심사시간 배열을 돌며 모든 심사관들이 mid분 동안 심사한 사람의 수(check_person)를 센다.

만약 check_person이 n이상이 되면 반복문을 멈춘다.

 

#업?
if check_person >= n:
    e = mid - 1
    answer = mid
# 다운?
else:
    s = mid + 1

check_person이 n보다 크면 범위 끝점(e)를 mid - 1로 설정하고 while문 처음으로 가서 다시 탐색한다.

check_person이 n보다 작으면 범위 시작점(s)를 mid + 1로 설정하고 while문 처음으로 가서 다시 탐색한다.

이렇게 반갈하면서 탐색을 진행하다 범위의 시작점, 끝점이 교차되면 while문을 종료한다.

 

 

새롭게 배운점/느낀점

• 만약 범위가 내가 설정하는게 아니라 배열이 주어진다면, 그 배열을 정렬해놓고 이분탐색 하는것이 실행속도가 더 빠르다.

• 이분탐색의 이론은 알았지만, 문제에 적용하기가 어려웠다.
• 이분탐색 유형의 문제를 많이 풀어보며 감을 잡아가는 과정이 필요할것같다.

 

더 나은 의견이나 궁금하신게 있다면 편하게 댓글 달아주세요 :)