TIL #7 - [algo] 프로그래머스_무지의 먹방 라이브 파이썬

Tami·2021년 8월 29일

TIL

목록 보기

8/9

보통 알고리즘은 tistory 블로그에 올리지만, 프로그래머스는 올리지 못하므로 여기서 정리해야겠다.
평일에는 매번 이것이코딩테스트다에서 아주아주쉬운문제를 딱1문제씩 골라 풀고 답안을 바로 보니까 공부를 너무 안하는 것같아서 주말에는 찐하게 알고문제를 풀어보기로 결심!

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

LV4- 그리디

첫 번째 시도

def solution(food_times, k):
    answer = 0
    cur_food=0
    cur_time=0
    
    while cur_time<= k:
        for idx,f in enumerate(food_times):
        
            if f!=0:
                cur_time+=1
                food_times[idx]-=1
                cur_food=idx+1
            else:
                continue

    if cur_time == k+1:
        return(cur_food)
    else:
        return(-1)

캬.. 깔끔하게 망햇다.
일단은

cur_food : 현재 음식
cur_time : 현재 시간

네트워크 장애와 현재 시간을 기준으로 진행
조건문
2-1. 만약 현재 음식이 0 이아니면 음식 먹기
2-2. 음식이 0이면 다음 음식 먹기

한가지 간과한 것은 fodd_times를 다 돌기 전 네트워크오류시간을 맞이한 경우를 처리하지 않았다.

두 번째 시도

def solution(food_times, k):
    answer = 0
    cur_food=0
    cur_time=0
    
    def isNotNetworkError(ct):
        if ct<= k:
            return True
        else:
            return False
    
    while isNotNetworkError(cur_time):
        for idx,f in enumerate(food_times):
            if f!=0:
                cur_time+=1
                food_times[idx]-=1
                cur_food=idx+1
            else:
                continue
            if isNotNetworkError(cur_time)==False:
                break
                

    if cur_time == k+1:
        return(cur_food)
    else:
        return(-1)

isNotNetworkError라는 네트워크오류를 확인하는 함수를 만든 후에
분기를 두번 처리할 수 있도록 변경했다.

fodd_times를 다 돌았을 때 네트워크 오류 시간(k)인지 확인
도는 와중에 네트워크 오류 시간(k)인지 확인

하지만 while + for + if 의 조합은 시간초과를 야기했다.

시간초과를 해결하기 위해 while을 없애고 직접 idx를 늘려가며 했지만 시간초과는 해결되지 안았고, 시간초과에 대한 풀이방법을 찾는 중에 k의 범위가 2*10^23으로 되어있어 k대로 탐색을 하면 무조건 효율성에 걸리게 됨을 깨달았다.

다른 풀이

🔗 이분탐색을 이용한 무지의 먹방라이브 풀이

위 블로그의 풀이에 따르자면,
k초까지 한번씩 다 도는게 아니라 접근 자체를 다르게 해야한다.

모든 음식에 소요되는 시간이 같다면
( food_times의 길이food_len) * ( food_times 1회 탐색횟수 ) = food_times 1회 돌며 음식을 다먹었을 때 시간
이어야 하지만,

food_times의 값들이 다르기 때문에 진행하다 다먹어버린 음식은 시간을 소요하지 않고 다음 음식으로 넘어가기 때문에 예상시간보다 먼저 마지막 음식에 도달하게 된다.

풀이 과정

이분탐색을 통해 모든 행에 뺄 수cutting를 구하자
food_times에서 뺄 수를 빼버린걸로 만들어버리자
새로 만든 food_times를 돌며 네트워크오류(k초)시 먹는 음식을 알아내자!

def solution(food_times, k):
    
    start,end = 0,100000000
    food_len, cutting, idx= len(food_times),0,0
    
    # 전체에서 뺄 수를 알아내기 
    while start <= end:
        mid = (start+end)//2
        last_second = food_len * mid
        
        for f in food_times:
            temp = f-mid
            if temp <0 :
                last_second += temp
        if last_second <= k:
            cutting, idx= mid, last_second
            start = mid+1
        else:
            end = mid-1
            
    # 모든 행에서 뺄수 빼주기
    food_times = [f-cutting for f in food_times]
    
    # k초 시에 먹고 있는 음식 알아내기
    for i in range(food_len):
        if food_times[i] > 0 and idx==k:
            return i+1
        else:
            if food_times[i]>0:
                idx+=1
    return -1