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

tami·2021년 8월 29일
2

TIL

목록 보기
8/9
post-thumbnail

보통 알고리즘은 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 : 현재 시간

  1. 네트워크 장애와 현재 시간을 기준으로 진행
  2. 조건문
    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라는 네트워크오류를 확인하는 함수를 만든 후에
분기를 두번 처리할 수 있도록 변경했다.

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

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

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


다른 풀이

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

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

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

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

풀이 과정

  1. 이분탐색을 통해 모든 행에 뺄 수cutting를 구하자
  2. food_times에서 뺄 수를 빼버린걸로 만들어버리자
  3. 새로 만든 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

느낀점

정말 단순히 요구사항을 그대로 코드로 구현해놓고 도대체 왜 시간초과가 나지? 하며 고민했었는데,
그냥 말을 코드로 옮기는 것이 아닌 효율적인 방법을 고민하는 것이 필수적이라는 걸 깨달았다.

  1. 효율을 고민하자
  2. 문제의 의미를 제대로 파악하자

이 문제만 2.5h 소요했다..^^
끝!

profile
자스베이더 Tami의 TILAND에 오신걸 환영합니다🗡

0개의 댓글