무지의 먹방 라이브 (42891번) - 프로그래머스 (Programmers)

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

프로그래머스

 

 

프로그래머스 - 무지의 먹방 라이브 (42891번)

난이도 : Lv 4

Time Complexity : O( NlogN )

알고리즘&자료구조 : Sorting (정렬), Stack (스택)

 

---

2019 KAKAO BLIND RECRUITMENT 기출문제이다.

 

 

< 전체 코드 >

def solution(food_times, k):
    food_times = [(time, i) for i, time in enumerate(food_times, start=1)]
    food_times.sort(key=lambda x: -x[0])
    cutoff = 0
    while food_times:
        while food_times[-1][0] == cutoff:
            food_times.pop()
            if not food_times:
                return -1
        cur = food_times[-1][0]
        if len(food_times) * (cur-cutoff) <= k:
            k -= len(food_times) * (cur-cutoff)
            food_times.pop()
        else:
            k %= len(food_times)
            break
        cutoff = cur
    food_times.sort(key=lambda x: x[1])
    return food_times[k][1] if food_times else -1

 

---

 

① 먼저 주어진 food_times에 각 원소의 index를 enumerate를 통해 추가하고,

food_times의 time 기준으로 내림차순 정렬한다.

(가장 소요시간이 적은 음식이 맨 뒤로 간다.)

(pop을 사용해서 stack 처럼 쓰기 위해서이다.)

food_times = [(time, i) for i, time in enumerate(food_times, start=1)]
food_times.sort(key=lambda x: -x[0])

 

 

 

② cutoff = 0 으로 초기화한다. 

현재 food_times의 마지막 원소의 time 값을 cur 로 설정한다. ( cur = food_times[-1][0] )

(cutoff 은 이전 단계에서 food_times의 time 최솟값을 의미한다.)

(마찬가지로 cur 은 현재 단계에서 food_times의 time 최솟값을 의미한다.)

 

현재 food_time 의 길이 len(food_times) 에 (cur - cutoff) 값을 곱해주고,

그 값이 현재 k 보다 작거나 같다면

k에서 len(food_times) * (cur - cutoff) 값을 빼준다.

(무지가 현재 회전판의 모든 음식들을 (cur - cutoff) 번 반복해서 먹을 수 있다는 의미이다.)

cutoff = 0
while food_times:
    while food_times[-1][0] == cutoff:
        food_times.pop()
        if not food_times:
            return -1
    cur = food_times[-1][0]
    if len(food_times) * (cur-cutoff) <= k:
        k -= len(food_times) * (cur-cutoff)
        food_times.pop()
    else:
        k %= len(food_times)
        break
    cutoff = cur

 

만약 현재 가장 적게 남은 음식의 time 값이 cutoff와 같다면,

그 음식들은 이전 단계에서 이미 모두 먹은 것이므로 food_times에서 제거한다.

while food_times[-1][0] == cutoff:
    food_times.pop()

 

만약 k < len(food_times) * (cur - cutoff) 라면,

무지는 현재 회전판에서 가장 적게 남은 음식도 다 먹지 못한다.

 

따라서, k를 현재 남은 음식의 개수인 len(food_times)로 나눈 나머지를 구하고 (rem),

현재 회전판의 음식들 중, 초기 index 기준으로 rem 번째에 위치한 음식이

무지가 k초 후에 먹을 음식이 된다.

 

만약 while 문을 모두 돌았을 때 food_times가 빈 리스트이거나,

while 문 중간에 food_times가 빈 리스트가 된다면,

무지는 모든 음식을 이미 다 먹었으므로 -1을 출력한다.

if not food_times:
    return -1

food_times.sort(key=lambda x: x[1])
return food_times[k][1] if food_times else -1