무지의 먹방 라이브

무지의 먹방 라이브
2019 KAKAO BLIND RECRUITMENT
1230명 완료

풀어보니 특별히 족보있는 알고리듬이 필요한 건 아니었고.
왕창 왕창 한꺼번에 처리해 주면 통과할 수 있었습니다. 
Level 3에 있어도 될 법한 문제

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

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

시간제한을 못 넘기겠지만 이해한 것이 맞는지 확인해 봅니다. 
다행히 잘 맞습니다. 

def solution(food_times, k):
    answer = time = food_num = 0
    while time <= k:
        if sum(food_times) == 0:
            return -1
        if food_times[food_num] > 0:
            food_times[food_num] -= 1
            print(f"{time}~{time + 1}초 동안 {food_num + 1}번 음식을 섭취한다 남은 시간은 {food_times}이다.")
            answer = food_num + 1
            time += 1
        food_num = (food_num + 1) % len(food_times)
    return answer

0~1초 동안 1번 음식을 섭취한다 남은 시간은 [2, 1, 2]이다.
1~2초 동안 2번 음식을 섭취한다 남은 시간은 [2, 0, 2]이다.
2~3초 동안 3번 음식을 섭취한다 남은 시간은 [2, 0, 1]이다.
3~4초 동안 1번 음식을 섭취한다 남은 시간은 [1, 0, 1]이다.
4~5초 동안 3번 음식을 섭취한다 남은 시간은 [1, 0, 0]이다.
5~6초 동안 1번 음식을 섭취한다 남은 시간은 [0, 0, 0]이다.

정확성  테스트
테스트 27 〉	통과 (3490.55ms, 10.9MB)
효율성  테스트
테스트 1 〉	실패 (시간 초과)
테스트 2 〉	실패 (시간 초과)

왕창 왕창 지우면 빠를 것 같습니다. 
왕창 왕창 지울 수 없는 부분까지 가면
위 코드를 이용해 1씩 지웁니다. 
하지만 실패.

1/10 수준으로 시간을 줄였는데도 실패라니.
스케치 수준이라 코드가 조잡합니다.
아무 생각 없이 딕셔너리를 썼던 것도 그닥...
튜플과 힙큐보다 빨랐던 건 함정..

def solution(food_times, k):
    answer = time = 0
    # prev_time = 0
    food_times = {i + 1: v for i, v in enumerate(food_times)}
    min_time = min(food_times.values())
    while k >= min_time * len(food_times) + time:
        # prev_time = time
        time += min_time * len(food_times)
        for key in tuple(food_times):
            food_times[key] -= min_time
            if food_times[key] == 0:
                del food_times[key]
        # print(f"{prev_time} ~ {time}초 동안 각 {min_time}개의 음식을 섭취한다. 남은 시간은 {food_times}이다")
        if not food_times:
            return -1
        min_time = min(food_times.values())
    while k >= time:
        for key in tuple(food_times):
            if time == k:
                return key
            answer = key
            # prev_time = time
            time += 1
            food_times[key] -= 1
            if food_times[key] == 0:
                del food_times[key]
            # print(f"{prev_time} ~ {time}초 동안 {key}번 음식을 섭취한다. 남은 시간은 {food_times}이다.")
            if not food_times:
                return -1
    return answer

파이썬 3.8부터 도입된 Assignment Expression을 쓰면 2줄은 더 줄일 수 있습니다.
심지어 보기도 깔끔합니다.... while문으로 for문 비슷하게 쓸 수도 있고.. 전 극호네요.. 
귀도형... 형이 옳았어...
https://www.python.org/dev/peps/pep-0572/
http://www.ciokorea.com/news/39153

def solution(food_times, k):
    answer = time = 0
    # prev_time = 0
    food_times = {i + 1: v for i, v in enumerate(food_times)}
    while k >= (min_time := min(food_times.values())) * len(food_times) + time:
        # prev_time = time
        time += min_time * len(food_times)
        for key in tuple(food_times):
            food_times[key] -= min_time
            if food_times[key] == 0:
                del food_times[key]
        # print(f"{prev_time} ~ {time}초 동안 각 {min_time}개의 음식을 섭취한다. 남은 시간은 {food_times}이다")
        if not food_times:
            return -1
    while k >= time:
        for key in tuple(food_times):
            if time == k:
                return key
            answer = key
            # prev_time = time
            time += 1
            food_times[key] -= 1
            if food_times[key] == 0:
                del food_times[key]
            # print(f"{prev_time} ~ {time}초 동안 {key}번 음식을 섭취한다. 남은 시간은 {food_times}이다.")
            if not food_times:
                return -1
    return answer

정확성  테스트
테스트 27 〉	통과 (29.34ms, 11.1MB)
효율성  테스트
테스트 1 〉	실패 (시간 초과)
테스트 2 〉	실패 (시간 초과)

생각해보니
모든 딕셔너리(또는 배열의) 시간 값을 변경하는데
시간이 많이 걸리는 것 같습니다. 

각 배열의 시간값을 변경하지 말고.. 
대신 경과 시간 변수를 만들어서 사용해야겠습니다. 
변수 하나만 수정하면 되니까요.. 

계속 최소값을 찾는 것 보단 sort 한번 하는 게 빠르겠고.. 
마지막에도 sort를 한번 해줘야 하니.. 
딕셔너리보다는 튜플를 쓰는 것이 편했습니다.

딕셔너리는 파이썬 3.6부터 비공식적으로,
3.7부터는 공식적으로 '순서'가 있습니다만.
소트가 바로 되지도 않고, 인덱스도 없고...
딕셔너리 관련 라이브러리 중에 뭔가 있을 것 같지만....

def solution(food_times, k):
    from collections import deque
    time = min_time = 0
    food_times = deque(sorted([(v, i + 1) for i, v in enumerate(food_times)]))
    while food_times:
        if k == time:
            return sorted(food_times, key=lambda a: a[1])[0][1]
        if k >= time + (food_times[0][0] - min_time) * len(food_times):
            time += (food_times[0][0] - min_time) * len(food_times)
            min_time = food_times[0][0]
        elif k >= time + 1 * len(food_times):  # 이 부분의 1을 키우는 게 해결책..
            time += 1 * len(food_times)  #
            min_time += 1  #
        else:
            return sorted(food_times, key=lambda a: a[1])[k - time][1]
        while food_times and food_times[0][0] == min_time:
            food_times.popleft()
        # print(f" ~ {time}초 동안 음식을 섭취한다. 남은 시간은 {food_times}이다")
    return -1

정확성  테스트
테스트 27 〉	통과 (1.33ms, 11MB)
효율성  테스트
테스트 1 〉	통과 (275.87ms, 160MB)
테스트 2 〉	실패 (시간 초과)

거의 구현을 했고.. 
효율성 2번 테스트에서 걸리는데.. 
[1,1,100000000000000000000000] 이런 식의 테스트 코드일 것 같네요.. 
중간에 하나씩 올리는 과정을 왕창 왕창으로 바꿔주면 될 것 같습니다. 

드디어 해결...

def solution(food_times, k):
    from collections import deque
    time = min_time = 0
    food_times = deque(sorted([(v, i + 1) for i, v in enumerate(food_times)]))
    while k != time:
        if k >= time + (food_times[0][0] - min_time) * len(food_times):
            time += (food_times[0][0] - min_time) * len(food_times)
            min_time = food_times[0][0]
        elif (k - time) // len(food_times) > 0:
            time += (k - time) // len(food_times) * len(food_times)
            min_time += (k - time) // len(food_times)
        else:
            return sorted(food_times, key=lambda a: a[1])[k - time][1]
        while food_times[0][0] == min_time:
            food_times.popleft()
            if not food_times:
                return -1
    return sorted(food_times, key=lambda a: a[1])[0][1]

테스트 1 〉	통과 (341.63ms, 40.5MB)
테스트 2 〉	통과 (78.22ms, 40.2MB)
테스트 3 〉	통과 (325.88ms, 40.1MB)
테스트 4 〉	통과 (318.22ms, 40.3MB)
테스트 5 〉	통과 (343.91ms, 40.4MB)
테스트 6 〉	통과 (298.60ms, 40.7MB)
테스트 7 〉	통과 (331.06ms, 40.2MB)
테스트 8 〉	통과 (346.07ms, 41.3MB)

Assignment Expression

def solution(food_times, k):
    from collections import deque
    time = min_time = 0
    food_times = deque(sorted([(v, i + 1) for i, v in enumerate(food_times)]))
    while k != time:
        if k >= time + (time_stack := (food_times[0][0] - min_time) * len(food_times)):
            time += time_stack
            min_time = food_times[0][0]
        elif (quotient := (k - time) // len(food_times)) > 0:
            time += quotient * len(food_times)
            min_time += quotient
        else:
            return sorted(food_times, key=lambda a: a[1])[k - time][1]
        while food_times[0][0] == min_time:
            food_times.popleft()
            if not food_times:
                return -1
    return sorted(food_times, key=lambda a: a[1])[0][1]

테스트 1 〉	통과 (284.39ms, 40.4MB)
테스트 2 〉	통과 (79.28ms, 40.3MB)
테스트 3 〉	통과 (318.55ms, 40.3MB)
테스트 4 〉	통과 (306.55ms, 40.2MB)
테스트 5 〉	통과 (308.27ms, 40.5MB)
테스트 6 〉	통과 (336.53ms, 40.8MB)
테스트 7 〉	통과 (349.50ms, 40.2MB)
테스트 8 〉	통과 (296.78ms, 41.2MB)

디큐를 안써도 되죠?

def solution(food_times, k):
    time = min_time = 0
    food_times = sorted([(v, i + 1) for i, v in enumerate(food_times)], key=lambda x: -x[0])
    while k != time:
        if k >= time + (time_stack := (food_times[-1][0] - min_time) * len(food_times)):
            time += time_stack
            min_time = food_times[-1][0]
        elif (quotient := (k - time) // len(food_times)) > 0:
            time += quotient * len(food_times)
            min_time += quotient
        else:
            return sorted(food_times, key=lambda a: a[1])[k - time][1]
        while food_times[-1][0] == min_time:
            food_times.pop()
            if not food_times:
                return -1
    return sorted(food_times, key=lambda a: a[1])[0][1]

테스트 1 〉	통과 (289.83ms, 49.6MB)
테스트 2 〉	통과 (91.36ms, 48MB)
테스트 3 〉	통과 (272.23ms, 49.5MB)
테스트 4 〉	통과 (197.92ms, 49.6MB)
테스트 5 〉	통과 (265.98ms, 49.6MB)
테스트 6 〉	통과 (282.85ms, 49.6MB)
테스트 7 〉	통과 (244.34ms, 49.6MB)
테스트 8 〉	통과 (279.32ms, 49.7MB)

디큐가 더 빠르군요.. --;