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

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

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

딕셔너리 + 정렬을 활용해서 문제를 풀었다. 효율성에서 아슬아슬하게 통과해서 더 좋은 풀이가 있을 것 같다.

 

알고리즘 :

1. 먹는 것이 종료되는 시간이 같은 음식을 dict를 통해 세어 준다. (defaultdict 활용)

2. 짧은 시간 순서대로 dict.items를 정렬한다.

    - food_times의 입력이 [6, 6, 1, 1, 2, 2, 3, 5] 일 경우 아래와 같이 정렬됨.

    - Tsort => [(1, 2), (2, 2), (3, 1), (5, 1), (6, 2)] (음식 다 먹는 시간, 그 음식의 개수)

3. 정렬된 Tsort 기준으로 for loop를 돈다.

    - ex) Tsort에서 1, 2 일 경우

    - 1만큼 시간 이후 2개의 음식을 다 먹게 됨 ->

      따라서, k에서 foodNum(현재 음식 개수) * 1(앞 전과의 시간 차이)을 빼준다.

    - 1이 지났으니 다음 루프부터는 그 음식은 다 먹었기 때문에 foodNum에서 2를 빼줌

    - 1만큼 시간이 흘렀으니 passTime에 +1 추가

4. 다음 음식과의 차이를 또 계산함

    - (1, 2) -> (2, 2) 2와 1 이므로 1만큼 차이가 남

    - (1, 2) 이후 1만큼의 시간이 흘렀다고 판단 따라서, k에서 foodNum(현재 음식 개수) * 1(앞 전과의 시간 차이)을        빼준다.

    - 마찬가지로 반복

5. 혹시 k 가 foodNum(현재 남은 음식 개수) * (앞 전과의 시간 차이) 보다 작으면 루프를 빠져나옴

6. 앞전과의 시간 차이가 1보다 클 수 있으므로

    - 예를 들어 남은 k 가 50이고 foodNum이 3일 때 앞 전과의 시간 차이가 20이라면 루프를 빠져나왔다.

    - 이 경우 while 문을 통해 3을 계속 빼줘도 되지만, 효율성을 늘리기 위해 몫과 나머지를 써주면 된다.

    - 우리가 원하는 것은 k가 3보다 작게끔 -> k = k % foodNum

    - passTime(흐른 시간) 은 적절히 증가 -> passTime += k // foodNum

 

설명을 잘 못하겠다.....

 

나의 풀이

from collections import defaultdict
def solution(food_times,k):
    time_dict = defaultdict(int)
    for time in food_times:
        time_dict[time] +=1

    Tsort = sorted(time_dict.items(), key = lambda x: x[0])
    passTime = 0
    foodNum = len(food_times)
    for i,t in enumerate(Tsort):
        curr, currCount = t
        time = curr - passTime
        if k < foodNum*time:
            break
        k -= foodNum*time
        passTime = curr
        foodNum -= currCount
    if foodNum == 0:
        return -1
    passTime += k // foodNum 
    k = k % foodNum
    for i,f in enumerate(food_times):
        if passTime < f:
            if k == 0 :
                return i+1
            k -= 1