[그리디 10] 무지의 먹방 라이브

미니 예제 1

1. 문제 설명하기.

food_times가 [3, 1, 2]이고, k=5인 경우이다.

2. 문제 해결하기.

이 미니 예제를 풀 때에는 count, idx를 변수로 두고 어떠한 과정이 진행됨에 따라 +1 처리를 해주었다.

Step 01. 무한 반복문으로 돌리고, 해당 food_times를 idx에서 -1 처리를 해준다. 그리고 count, idx를 +1 처리한다.
Step 02. idx가 마지막 인덱스를 넘어가는 경우에는 다시 처음으로 돌려준다. (idx=0)
Step 03. 해당 idx의 food_times가 0인 경우에는 idx를 +1 처리한 뒤에 작업을 진행한다.
Step 04. count가 k가 되면 반복문을 탈출한다.

# 미니 예제 1 : food_times=[3,1,2], k=5인 경우

food_times=[3,1,2]
idx=0
count=0

while True:
    food_times[idx]-=1
    print(idx)
    print(food_times)
    idx+=1
    count+=1
    if idx==3:
        idx=0
    if food_times[idx]==0:
        idx+=1
    if count == 5:
        break

코드를 일반적으로 표현하면 아래와 같다.

def solution(food_times, k):
    idx=0
    vacant_list=[0]*len(food_times)
    count=0
    
    while True:
        if count == k:
            break
        food_times[idx]-=1
        print(idx)
        print(food_times)
        idx+=1
        count+=1
        if idx==len(food_times):
            idx=0
        if food_times[idx]==0:
            if idx==len(food_times)-1:
                idx=0
                food_times[idx]-=1
            idx+=1
        if food_times[idx]==vacant_list:
            return -1
    return food_times[idx]
    
solution([3,1,2], 5) 

solution([2,9,10], 7) 를 넣어봤는데, 성공하였다.

미니 예제 2

1. 문제 설명하기.

food_times=[8,6,4]이고, k=15인 경우이다.

2. 문제 해결하기.

위와 동일하다.

# 미니 예제 2 : food_times=[8,6,4], k=15인 경우

def solution(food_times, k):
    idx=0
    vacant_list=[0]*len(food_times)
    count=0
    
    while True:
        if count == k:
            break
        food_times[idx]-=1
        print(idx)
        print(food_times)
        idx+=1
        count+=1
        if idx==len(food_times):
            idx=0
        if food_times[idx]==0:
            if idx==len(food_times)-1:
                idx=0
                food_times[idx]-=1
            idx+=1
        if food_times[idx]==vacant_list:
            return -1
    return food_times[idx]
    
solution([8,6,4], 15)

최적의 일반화

1. 문제 설명하기.

위와 동일하다.

2. 문제 해결하기.

def solution(food_times, k):
    idx=0
    vacant_list=[0]*len(food_times)
    count=0
    
    while True:
        if count == k:
            break
        food_times[idx]-=1
        print(idx)
        print(food_times)
        idx+=1
        count+=1
        if idx==len(food_times):
            idx=0
        if food_times[idx]==0:
            if idx==len(food_times)-1:
                idx=0
                food_times[idx]-=1
            idx+=1
        if food_times[idx]==vacant_list:
            return -1
    return food_times[idx]

하지만 이렇게 풀이하면 프로그래머스에서는 오류라고 뜬다.
여기서 함수가 return을 이용하기 때문에, print()를 이용하여 함수를 출력했는데 런타임 에러가 뜬다. 알고리즘 자체가 잘못된 케이스인 것 같다.

3. 책에 나와있는 최적의 일반화

큐를 이용하여 풀이한다고 나와있다.