[문제 풀이] 무지의 먹방 라이브

해결 과정

와 일단 ㅋ ㅋ ㅋ 4번 이상을 다시 짰다. 

정확성 + 효율성 문제라 정확성만 맞으면 통과가 안된다. 

1. 효율성 있길래 첫 풀이는 나름 고심해서 짰는데 정확성 자체가 통과를 다 못했고,

2. 다음 풀이는 정확성은 모두 맞으나, 효울성이 다 안나왔다. 

그래서 생각해낸 IDEA. 최소인 숫자를 모두 건너 뛰면 되겠다 -> 카카오 해설을 보니 이게 맞다.

3. 그래서 이 방식대로 2를 변경했는데 역시나 효율성이 다 안나온다. 

4. 이코테 + 카카오 해설 방식으로 다시 짰는데 와 여기서 스스로 짜려니까 빼먹은 부분이 많았다. 

어떤 부분이냐면, 효율성을 위해 시간을 빼주지 않고 따로 변수로 관리하도록 하는데, 이를 계산하는 부분이 난감했다. ㅋ

 

 

나의 풀이

import heapq

def solution(food_times, k):
    # 못하는 경우 미리 제거
    if sum(food_times) <= k:
        return -1 

    count = 0

    queue = []
    
    for idx, value in enumerate(food_times):
        heapq.heappush(queue, ((value, idx+1))) # (시간, 번호) 그래야 시간 순으로 정렬되어 들어감

    previous = 0

    while len(queue) * (queue[0][0] - previous) + count <= k:
        food = heapq.heappop(queue)
        newCount = (food[0] - previous) * (len(queue) + 1)
        previous = food[0]
        count += newCount
        
    remainedFoods = sorted(queue, key= lambda x: x[1])
    return remainedFoods[(k - count) % len(remainedFoods)][1]

print(solution([3, 1, 2], 5))

 

다른 풀이

GitHub - ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체

2019 카카오 신입 공채 1차 코딩 테스트 문제 해설

IDEA

우선순위 큐. 순서가 정해져있는 자료구조.

이 구조는 넣고 뺄 때, O(logN)의 시간을 갖는다고 한다. 

https://www.daleseo.com/python-priority-queue/

priorityQueue, heapq

 

여기서는 heapq를 사용했다.

 

heapq에서 정렬의 방식을 커스텀하고 싶을 때?

(정렬key, ..) 이런식으로 넣으면 된다.

 

효율성 정답률 4% ㅋ ㅇㅋ