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

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

시뮬레이션으로 풀이를 진행하려 하였으나, 입력 조건의 범위가 너무 크기에 시간초과 발생을 예상했습니다.

많은 인원의 연산을 위해 이분탐색을 이용하였습니다.

2) 알고리즘

• 이분탐색

3) 풀이 코드

사용 언어 - Python

def solution(n, times):
    times.sort()                # 이분 탐색을 위한 정렬
    answer = 0
    
    l, r = 0, times[-1] * n     # 모든 심사관의 소요되는 최소 시간, 최대 시간
    while l <= r:               
        mid = (l+r) // 2        # 모든 심사관이 mid 분을 이용하여 심사하게 될때
        tmp = 0
        for e in times:
            tmp += mid // e     # 각 심사관들이 mid 분을 이용해 심사했을때 각자 심사 가능한 인원 추가

            if tmp >= n:        # 현재 심사관까지 심사했는데, 모든 인원 심사가 가능한 경우
                answer = mid    # 현재 전체 소요 시간 저장
                r = mid - 1     # 더 짧은 시간으로 가능한지 탐색을 위한 설정
                break
        else:                   # 모든 심사관이 mid 분 동안 모든 인원 심사가 불가능하면
            l = mid + 1         # 더 많은 시간으로 가능한지 탐색

    return answer

print(solution(6, [10, 7]))

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

단순 시뮬레이션으로 구현하는 경우 시간초과가 예상되어 프로그래밍하지 못했습니다.

이분 탐색을 이용하여 풀어야 했으나, 어떤것을 기준으로 최저점과 최고점을 정하고 중간값을 정하는지 어려움을 겪었습니다.

(1) 참고 사이트

• 블로그
  위 문제에 이분탐색을 적용시키는 방법을 학습했습니다.
  모든 심사관이 모든 인원을 심사하는데 소요되는 최소 시간과 최대 시간을 정하여 그 중간값을 찾아나가는 방식을 학습했습니다.

2) 새롭게 학습한 내용

기존 이분 탐색은 특정 범위에서 특정한 숫자를 찾을때 많이 이용하였으나, 이번 기회를 통해 특정 범위의 숫자를 찾는 문제에서만 사용가능한것은 아니라는것을 알게 되었습니다.

---

🔗 문제 링크

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

코딩테스트 연습 - 입국심사

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다