[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코2파
Rule :
하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능
START :
[3코1파] 2023.01.04~ (125일차)
[4코1파] 2023.01.13~ (116일차)
[1스4코1파] 2023.04.12~ (27일차)
[1스4코2파] 2023.05.03 ~ (6일차)
Today :
2023.05.08 [125일차]
프로그래머스 LV 3.
입국심사
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명 이하입니다.
입출력 예
입출력 예 설명
가장 첫 두 사람은 바로 심사를 받으러 갑니다.
7분이 되었을 때, 첫 번째 심사대가 비고 3번째 사람이 심사를 받습니다.
10분이 되었을 때, 두 번째 심사대가 비고 4번째 사람이 심사를 받습니다.
14분이 되었을 때, 첫 번째 심사대가 비고 5번째 사람이 심사를 받습니다.
20분이 되었을 때, 두 번째 심사대가 비지만 6번째 사람이 그곳에서 심사를 받지 않고 1분을 더 기다린 후에 첫 번째 심사대에서 심사를 받으면 28분에 모든 사람의 심사가 끝납니다.
문제 풀이 방법
렙 3 지만 LeetCode에서 binary Search 3문제 풀고 와서 감은 좀 잡을 줄..
하지만 저런 식으로 직관적으로 안나오는 문제는 또 어려운 것이 함정
처음에 렙 0따리 처럼 풀었다가
Binary Search 다시 맹연습 하고 옴
=> https://github.com/heyggun/Coding_test/tree/main/LeetCode/Algorithm%20Plan%2014
일단은 binary search로 푼 방법은
주어진 times 리스트에 가장 오래 걸리는 시간을 가져와서 binary search 의 범위로 지정함
가장 오래걸리는 시간에 사람 수(n)을 곱해줘서 1분~에서 n*max(times) 를 범위로 지정함
binary search 범위 -> 1~ n * max(times)
그 이후에 binary search 종료 조건인 값을 찾을 때까지 while문을 돌려주고 (start<=end)
주어진 binary search에서의 중간값 mid에 따라 주어진 time 에 대한 몫으로
처리할 수 있는 최대 사람 수를 구한다.
최대 사람 수가 주어진 n보다 크다면, 시간을 줄이고 n 보다 작다면 주어진 시간을 늘려서
(전자는 end를 mid-1, 후자는 start mid+1로 해줌) 루프를 반복하면 되는데,
여기서 걸리는 사람의 수가 주어진 n보다 클때
answer가 mid로 지정해야 하는 이 부분을 잘 몰라서 이해하기 힘들었음..
일단 내가 어려워하는 부분은 binary search가 딱 떨어지지 않고 최대한 가까운 값을 구해야 할때
break 하기 전의 point가 start 인지 start+1 인지 end+1 인지 end 인지
감을 잘 못잡는 거 같기도 하다 (잣됨..)
일단 여기서는 걸리는 최소의 값을 구해야하므로 answer를 mid로 잡고 있어야 함..
내 코드
def solution(n, times):
answer= 0
start, end = 1, n*max(times)
while start<=end:
mid = (start+end)//2
people = 0
for time in times:
people += mid//time
if people>=n:
answer = mid
end = mid-1
else:
start = mid+1
return answer증빙
다른 사람 풀이
여담
사실 프로그래머스 lv 2. 양궁대회 풀다가 leetcode로 도망쳤었다가
leetcode 생각보다 좋은데...(?) 라고 생각함..
일단 leetcode 먼저 풀고 유사한 문제 프로그래머스로 와서 구현하면 될 듯
