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

 문제

 

programmers.co.kr/learn/courses/30/lessons/42891

코딩테스트 연습 - 무지의 먹방 라이브

 

 

 

 문제 상황

 

- 주어진 리스트는 무지가 먹어야 할 음식의 종류(인덱스)와 그 양(요소)를 의미하고 하나씩 음식을 먹어가며 k초 후 방송이 멈춘 후 다시 방송이 재개되었을 때 먹을 다음 음식을 찾는다.

 

 

 

 해결 전략

 

- 정확성은 매우 쉬운 문제이지만 효율성은 정답률 5.52%의 매우 어려운 문제였다. 논리적인 방법은 생각해냈지만 구현 과정에서 반례를 생각해야하고, 효율성에서 문제가 생기는 부분을 해결하는 방법을 고안하기가 까다로웠다.

 

 

 

 코드

 

def solution(food_times, k):
    # 음식의 총량
    total = sum(food_times)
    # 남은 음식보다 k가 크면 -1을 출력
    if total <= k:
        return -1
    for i, ele in enumerate(food_times):
        food_times[i] = (ele, i)
    food_times.sort(key= lambda x: (x[0],x[1]))
    ft_len = len(food_times)
    idx = 0
    # 연산 전에 빼줘야할 숫자
    discount = 0
    while True:
        # idx번째로 작은 요소의 남은 음식
        temp = food_times[idx][0] - discount
        # 만약 남은 음식의 길이*temp 보다 먹어야될 횟수가 크면 그만큼을 빼준다.
        if temp*ft_len <= k:
            discount += temp
            # 첫번째 값만큼 전체 빼주기 때문에 
            food_times[idx] = (0, food_times[idx][1])
            k -= temp*ft_len
            ft_len -= 1
            idx +=1
        # 만약 모든 요소를 돌 수 없다면
        else:
            r = k%ft_len
            food_times.sort(key=lambda x : x[1])
            for i in range(len(food_times)):
                if food_times[i][0] != 0:
                    r -= 1
                if r == -1:
                    return i+1
            
print(solution([3,1,2], 5))
 
# 정확도
 
# def solution(food_times, k):
#     total = sum(food_times)
#     idx = 0
#     while True:
#         if food_times[idx%(len(food_times))] != 0:
#             if k == 0:
#                 return (idx%len(food_times)) + 1
#             else:
#                 k -=1
#                 food_times[idx%(len(food_times))] -= 1
#                 total -= 1
#         if total == 0:
#             return -1
#         idx += 1
            
 
# print(solution([3,1,2], 5))

 

 

 

 해설

 

- 여기서 포인트는 첫번째로 정렬을 한다는 것이다. 정렬을 최초 인덱스와 함께 저장해서 활용하고 중요한 것은 마지막 연산에서 다시 인덱스를 기준으로 정렬하여 원하는 값을 찾는 것이다.

 

- 두번째 포인트는 먹을 음식이 없는 조건이다. 처음에는 while문 안에 조건을 넣었지만 속도 이슈가 발생하였다. 생각해보면 전체 음식의 총 합보다 먹어야 될 수 k가 많을 때 문제가 발생하므로 O(N)으로 총 합만 계산해주면 O(1)로 판단할 수 있는 문제여서 반복문 밖에 배치하였다.

 

- 세번째는 길이를 매번 구하는 것이 아니라 한번 구해 저장하고 그 변화를 보며 계산해준다는 것이다. 

 

- 네번째는 discount 변수이다. 원래는 요소를 한번에 모두 빼는 연산을 반복하여 log(N)의 시간이 while문 안에서 계속 반복되었다. 하지만 discount 변수를 통해 새로 뺄 때에는 이미 이전에 뺀만큼 빠져있어야하므로 discount를 먼저 빼주고 discount를 갱신하는 구조로 작업하였다.

 

 

 

 새로 학습한 것 & 실수 

 

- 모든 코드를 작성하고 idx를 1 더해주는 코드를 빼놓았다. 디버그 과정에서 플로우를 따라가며 idx += 1이 빠져있는 것을 발견하였다. 플로우를 좀 더 세분화 한 뒤에 코드를 짜기 시작해야한다. 반복조건 등을 좀 더 면밀히 봐야할 필요가 있다.

 

- 내가 느낀 알고리즘 문제풀이의 순서

 

1) 예시를 보며 논리 흐름을 따라가보고 순서를 정리한다.

 

2) 1번의 논리 흐름과 순서를 조금더 구체화하며 필요한 변수 등을 결정한다.

 

3) 2번을 바탕으로 조금더 구체화 된 코드 모양의 흐름을 결정한다.

 

4) 코드를 짜본다.

 

5) 오류가 발생할 경우 디버깅을 하는데 중간 중간에 print구문으로 중간 결과를 확인하며 디버깅한다.

 

6) 오류 해결이 어렵거나 고쳐야할 부분의 크기가 크다면 계속 작은 부분을 바꾸는게 아니라 2번으로 다시 갈 필요가 있다.