무지의 먹방 라이브 - 프로그래머스 - Level 4

무지의 먹방 라이브 - 프로그래머스 - Level 4

너무 어려웠다. 이것이 코딩 테스트다 교재에서 그리디 문제로 분류되어있다. 난이도가 1/3 가장 쉬운 난이도로 책정되어 있는데 정확성 테스트만 따진 난이도인가 싶다. 아직 정석 풀이를 보지 않아서 얼마나 간단하게 풀 수 있는 지는 모르겠다.

먼저 sum(food_times)와 min(food_times), max(food_times)를 구한다. 효율성 테스트 때문에 제한시간이 빠듯하므로 일일히 루프로 구현했다.

total = 0
_max = 0
_min = 100000001

for item in food_times:
    if item > _max:
        _max = item
    if item < _min:
        _min = item
    total += item

더 섭취할 음식이 없는 경우 -1을 반환한다.

if k >= total:
    return -1

이진 탐색을 사용했다. 무지가 회전판을 몇 번 돌려 먹었는 지 이진 탐색한다. 시작 값은 food_times의 최솟값, 끝 값은 food_times의 최댓값이다.

start = _min
end = _max
mid = (start + end) // 2

final 리스트에는 마지막 회전판에 무지가 먹을 수 있는 음식을 추가한다. index 변수는 final 리스트의 유효 인덱스를 알려준다. tempk에는 k의 값을 저장하고, 마지막 회전 바로 직전 까지의 식사까지 걸린 시간을 빼서 다음 탐색 범위를 결정한다. tempk가 0보다 작으면 회전판을 너무 많이 돌린(food_times 배열을 너무 많이 순회한) 것이다. tempk가 0이면 딱 회전판을 완전히 돌리고(food_times 배열을 끝까지 순회하고) 다음 식사를 하려할 때 방송이 중단된 경우이다. 그리고 tempk가 0보다 크면 우리가 원하는, 무지가 몇 번 회전판을 돌렸는 지의 값을 얻을 수도 있고, 아니면 너무 회전판을 조금 돌린(food_times 배열을 너무 조금 순회한) 것일 수도 있다.

final = [0] * len(food_times)
while start <= end:
    mid = (start + end) // 2
    tempk = k
    index = 0
    for i in range(len(food_times)):
        if food_times[i] > mid-1:
            tempk -= mid - 1
            final[index] = i+1
            index += 1
        else:
            tempk -= food_times[i]
    if tempk < 0:
        end = mid - 1
    elif tempk == 0:
        for i in range(len(food_times)):
            return final[0]
    else:
        if tempk < index:
            return final[tempk]
        start = mid + 1
return final[tempk]