[6주차_목요일] 입국심사

[icegosimperson]

• 사이트 : 프로그래머스(PG)
• 문제: 입국심사
• 번호: 43238

  🤔 시간복잡도 고려사항
  💡 풀이 아이디어

[Jewan1120]

🤔 시간복잡도 고려사항

• 심사관은 1명 이상 100,000명 이하 → 10^5이므로 O(N logN)으로
• 이분 탐색 or 매개변수 탐색

💡 풀이 아이디어

• 모든 사람이 심사를 받는데 가능한 모든 시간대에서 최솟값을 반환하는 문제이므로 매개변수 탐색
• 매개 변수 : 심사에 필요한 시간
• 결정 함수 : 해당 시간에 n명 이상 심사 했는가?
• Lower Bound를 반환해야 하므로 결정 함수를 만족하면 왼쪽 탐색으로 이어나감

이분 탐색, 매개 변수 팟 보면 팍!

[yeongleej]

🤔 시간복잡도 고려사항

• 사람수 <= 1,000,000,000
• 심사관 수 <= 100,000

=> 완전탐색은 불가 XX, O(NlogN)으로 해결할 수 있는 이분탐색 생각해보기

💡 풀이 아이디어

• 구해야하는 것: 모든 사람이 심사받는데 필요한 최소시간
  • 시작값: 1분
  • 끝값: 가장오래걸리는 사람의 심사시간 * 총 인원수
• 매개변수 탐색: 어떤 시간안에 n명을 심사할 수 있나? 없나?
  • 현재시간(mid)에 심사할 수 있는 인원수 구하기
  • 각 심사위원이 심사할 수 있는 사람의 수 = 실행시간(mid) / 심시위원의 심사시간(times[i])

[baexxbin]

🤔 시간복잡도 고려사항

• 사람수 <= 1,000,000,000 (10^9)
• 심사관 수 <= 100,000 (10^5)
• O(NlogN)
• 심사 시 걸리는 시간, 사람 수 모두 10^9로 공간 복잡도도 생각하기 → long형

💡 풀이 아이디어

• 이분탐색, 매개변수 탐색
  • 주어진 시간 내 n명 이상의 사람 처리할 수 있는지
  • 변수:
    • 시간
    • 이때 최대 시간은 가장 오래걸리는 심사 시간* 총 사람 수
  • 조건(canCheck()):
    • 해당 시간 내 n명 이상 처리 가능한지
    • mid/time의 몫 카운트

[icegosimperson]

🤔 시간복잡도 고려사항

• 시간 복잡도 : n, m<= 10^9
• -> 완전 탐색하면 시간 초과 될 것, 이분 탐색으로 시간 복잡도 줄여주기 O(N logN)

💡 풀이 아이디어

• 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 구하는 문제
• 이분탐색으로 푼 이유 : 주어진 심사 기간안에 n명이 심사받을 수 있는 최소 시간 찾기
• 시간의 범위를 줄여서 Lower Bound
• left : 가장 짧게 걸리는 상담 시간
• right : 최악의 시간(가장 오래 걸리는 상담 시간* 상담자 수)

[KodaHye]

🤔 시간복잡도 고려사항

• 1 <= 입국심사를 기다리는 사람 <= 1_000_000_000
• 1분 <= 입국 심사 시간 <= 1_000_000_000
• 1명 <= 심사관 <= 100_000

입국 심사 사람 수, 심사 시간에 대해 O(logN), 심사관의 수에 대해 O(NlogN)으로 해결할 수 있는 방법을 찾아야 됨

💡 풀이 아이디어

• 총 걸린 시간에 대한 사람 수를 구하며 s, e 조절해주기 : O(logN) < 1억
• 모든 사람들이 심사를 받는데 걸리는 시간의 최솟값을 구해야 하므로 Lower Bound를 구해야 됨

[yeahdy]

🤔 시간복잡도 고려사항

• 알고리즘: 이분탐색
• 시간복잡도: 입국심사를 기다리는 사람(N) 1명 이상 1,000,000,000명 이하 10^9 심사 시간 1분 이상 1,000,000,000분 이하 10^9
  • 이분탐색으로 풀이할 경우 O(logN) > O(log(최대심사시간*N))
  • 심사원의 수(M)만큼 순회하므로 O(MlogN)

💡 풀이 아이디어

• 모든 사람이 심사를 받는데 걸리는 최소시간 > lowerBound
• 끝값을 결정하는 기준?
  • 가장 큰값으로 최대 심사 시간 (가장 긴 심사시간*총인원수)
• 최소시간에 n명의 심사를 할 수 있는지?없는지?
  • 최소 시간이 될 수 있는 후보는 중간값 (최소 심사시간+최대 심사시간)/2 으로
  • 중간값이 최소시간이 될 수 있도록 이분탐색을 통해 간격을 조정을 해야함