[2019 KAKAO BLIND RECRUITMENT] Lv.1 무지의 먹방 라이브

https://school.programmers.co.kr/learn/courses/30/lessons/42891?language=python3 

프로그래머스

 

 

1. 해결방법

<효율성에서 실패한 방법>

기본적으로 위와 같은 로직으로 흘러가는데, 

본인은 크게 while 문으로 돌려서 종료 지점과 food_times의 인덱스 값이 0인 경우의 if 문  + while 문을 돌려서 네트워크 에러 발생 시 인덱스 위치 값을 반환하도록 하였다.

아마 2중 반복문을 사용해서 시간복잡도가 O(N^2)이기에 효율성 부분에서 문제가 있다고 생각한다.

< 해결한 방법 >
다른 분들의 해설을 참고하였더니 그리드 알고리즘 즉, 최선의 방법을 택해서 해결하는 방법으로 접근하였다.
heapq를 이용해서 음식 섭취 시간이 짧은 음식부터 해결해서 주어진 시간 k를 감소시켜나가는 방법으로 했다.

1. 모든 음식의 정보 -> (음식 섭취 시간, 음식의 넘버)를 heap에 삽입한다. -> 섭취 시간이 가장 짧은 데이터가 앞에 정렬됨.
2. heap[0]번째의 음식 섭취 시간을 계산한다. (이전의 섭취 시간을 현재의 섭취 시간에서 빼줘야 한다)
3. 푸드 리스트의 개수를 -1 하고, k 값도 (섭취 시간 * lens) 만큼 빼준다. previous 이전의 음식 섭취 시간을 갱신한다.
4. 더 이상 k를 빼줄 수 없을 때, 음식 넘버를 기준으로 sort 하고 (k * len) 를 해주면 몇 번째 음식 넘버인지 값이 나온다. 

역시 카카오 문제 답게 아이디어 떠오르기가 쉽지 않았다.
처음에는 무식하게 처리했다가 효율성에서 광탈하였는데, 그리디 알고리즘으로 접근을 하는 것을 알더라도 완벽하게 아이디어가 해결되지도 않았고 값 처리하는데 있어서도 많이 헤맸다.....
확실히 더 많이 풀어봐야할 것 같다.

 

 

2. 정답코드

(1) 효율성 실패 코드

def solution(food_times, k):
    answer = 0
    
    time = 0
    idx = 0
    while True:
        # 종료
        if time > k:
            break
        
        # idx 초기화
        if idx >= len(food_times):
            idx = 0
            
        # 0 방지
        if food_times[idx] == 0:
            while True:
                if food_times[idx] != 0:
                    break
                idx  += 1

                if idx >= len(food_times):
                    idx = 0
        
        food_times[idx] -= 1
        idx += 1
        time += 1
        
    answer = idx
        
    return answer

 

(2) 해결한 코드

def solution(food_times, k):
    import heapq
    answer = -1
    heap = []
    
    for i in range(len(food_times)):
        heapq.heappush(heap, (food_times[i], i + 1))
    
    lens = len(food_times)
    previous = 0
    
    while heap:
        food_time = (heap[0][0] - previous) * lens
        print(heap, food_time)
        
        if k >= food_time:
            k -= food_time
            lens -= 1
            previous, _ = heapq.heappop(heap)
        else:
            result = sorted(heap, key=lambda x : x[1])
            answer = result[k % lens][1]
            break
        
    return answer