이진탐색 문제로 4일정도 골머리를 썩고있는데요.
아래는 문제입니다!!
홈플러스에 n명의 고객과 m개의 계산대가 있다. 각 계산대에
는 각 1명의 직원만 존재하며, 각 직원들은 계산을 처리하는
시간이 모두 다르다. (예: 1번 직원 7분, 2번 직원 10분, …)
▪ n명의 고객들은 한 줄로 대기하고 있으며, 맨 앞 고객부터 한
명씩 비어있는 계산대에 있는 직원에게 가서 물건 계산을 할
수 있다.
• 이 때, 비어 있는 계산대 (A)가 있더라도, 더 빨리 계산을 처리할
수 있는 다른 직원 (B)이 있는 경우, B가 serving하는 고객이 끝
날 때까지 기다렸다가 B로 방문하여 더 빨리 계산하고 나갈 수
있다.
• 예: A 처리시간 10분, B 대기시간 2분 +처리시간 3분 일 경우 B
선택
▪ N명이 모두 계산하고 나가는 데까지 걸리는 “최소시간”을 구
하는 함수 min_times_all_served을 작성하시오
min_times_all_served(n, serving_times)
• n (integer): serving할 고객의 수 (1 ≤ n ≤ 1,000,000,000)
• serving_times (integer list): 각 직원이 serving하는데
소요되는 시간들
• 예) 직원이 총 2명 있고, 각각 serving time이 7분, 10분이라면 →
[7, 10]
• 각 직원이 serving하는데 걸리는 시간 (즉, serving_times의 요소
값) 범위는 1분 이상 1,000,000,000분 이하.
• 직원의 수는 최소 1명 이상, 100,000명 이하.
▪ 입출력 예
1. min_times_all_served(2, [1, 2]) → 2
2. min_times_all_served(3, [1, 99, 99]) → 3
3. min_times_all_served(6, [7, 10]) → 28
ex)min_times_all_served(6, [7, 10]) → 28
• 제일 앞에 있는 첫 두 사람이 바로 물건 계산 시작
• 7분이 되었을 때, 첫 번째 계산대가 비게 되고 3번째 사람
이 물건 계산 시작
• 10분이 되었을 때, 두 번째 계산대가 비게 되고 4번째 사람
이 물건 계산 시작
• 14분이 되었을 때, 첫 번째 계산대가 비게 되고 5번째 사람
이 물건 계산 시작
• 20분이 되었을 때, 두 번째 계산대가 비지만 6번째 사람이
그곳에서 계산하지 않고 1분을 더 기다린 후에 첫 번째 계
산대로 가면 28분에 모든 사람의 계산이 끝남
아래는 힌트입니다..!!
이분 탐색으로 풀 것 (동작 시간 제한)
▪ 이분 탐색 문제의 해결 순서 참고 (13~14주차)
• 어떤 값을 이분 탐색으로 찾을 것인가?
→ 모든 사람이 마트에서 계산을 끝낸 시간의 최소값
• 해당 값의 범위는 무엇인가?
→ ????
• 문제의 답을 만족하는 조건은 무엇이며, 어떻게 검증
할 것인가?
→ ????
• 분할된 리스트 중 낮은 쪽/높은 쪽을 어떤 기준으로
선택할 것인가? (경계 조건 주의!)
→ ???
마지막으로... 제가 여태껏 작성한 미완성 코드입니다ㅠ 이것저것 시도하다보니 쓸모없는 부분도 꽤나 많을거에요 ㅠㅜ 제가 전달해드릴수 있는건 최대한 요약해서 올립니다 ㅠㅜ 읽어주셔서 감사하며, 푸실 수 있다면 부탁드리겠습니다....!!!!!!!!!
def min_times_all_served(n, serving_times):
import random
N = len(serving_times)
sorted_serving_times = sorted(serving_times) #serving_times 리스트를 정렬
print(f'처리시간들 : {sorted_serving_times}') #처리시간들 나타내보기
p=0
k=p+1
# r = 처리시간 + 차이나는 시간(차이나는 시간 = list[n+1] - list[n])
r = sorted_serving_times[p]+(sorted_serving_times[p+1]-sorted_serving_times[p])
d = (sorted_serving_times[p]*k-sorted_serving_times[p+1]) + sorted_serving_times[p]
print(r)
print(d)
q=list(map(lambda x:x+r,sorted_serving_times))
w=list(map(lambda x:x+d, sorted_serving_times))
print()
print(q)
print()
low=0
high = len(sorted_serving_times) - 1
'''
def summing(f):
return reduce(lambda x,y: x+y, f)
fr = summing(r)
fd = summing(d)
'''
try:
while len(q) == len(sorted_serving_times):
mid = (high+low) // 2
if len(q) == len(sorted_serving_times):
return mid+1
elif r > d:
p += 1
high = mid-1
else:
p += 1
low = mid + 1
except Exception as e:
print(e)
print('잘못됨')
if __name__ == '__main__':
print(min_times_all_served(2, [1, 2])) # Should be 2
print(min_times_all_served(3, [1, 99, 99])) # Should be 3
print(min_times_all_served(6, [7, 10])) # Should be 28