# 테페리넷

## 테페리넷

### 관리자 전용

ps:problems:programmers:42891

# 무지의 먹방 라이브

ps
링크https://programmers.co.kr/learn/courses/30/lessons/42891
출처프로그래머스
문제 번호42891
문제명무지의 먹방 라이브
레벨Level 4
분류

정렬

시간복잡도O(nlogn)
인풋사이즈n <= 200,000
사용한 언어Python
해결날짜2020/12/21

## 풀이

• food_times를 오름차순으로 정렬한 배열을 f라고 하자. 음식의 갯수는 n이라고 하자.
• 처음에는 모든 음식이 아직 남아있다. n개의 음식을 f만큼씩 먹고 나면, 이제 남은 음식의 갯수는 n-1이 된다. 이제 n-1개의 음식을 f-f만큼씩 먹고 나면, 남은 음식의 갯수는 하나 줄어서 n-2가 된다.
• 이렇게 시간을 더해 나가면서 K보다 커지는 시간을 찾으면, 음식이 몇개 남았을때 K 시간이 되는지 알 수 있다.
• 다시 말하면, 아래를 만족하는 i를 찾는다
• n*f + (n-1)(f-f) + … + (n-i)(f[i]-f[i-1]) ≤ K < n*f + (n-1)(f-f) + … + (n-i-1)(f[i+1]-f[i])
• 이 말은, 음식이 n-i개 남은 시점에서 남은 시간이 K-f[i]라는 의미이니, n-i 개의 남은 음식 중, (K-f[i])%(n-i) 번째의 음식의 번호를 출력하면 된다.
• 처음 food_times를 정렬하는데에 O(nlogn)이 걸리고, i를 구하는 데는 O(n)이 걸린다. 그래서 총 시간 복잡도는 O(nlogn)

## 코드

"""Solution code for "Programmers 42891. 무지의 먹방 라이브".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/42891
- Solution link: http://www.teferi.net/ps/problems/programmers/42891
"""

def solution(food_times, k):
answer = -1
food_count = len(food_times)
time_and_nums = sorted((t, i) for i, t in enumerate(food_times))
is_remaining = [True] * food_count
remaining_food_count = food_count
remaining_time = k
prev_time = 0
for cur_time, num in time_and_nums:
spent_time = remaining_food_count * (cur_time - prev_time)
if spent_time > remaining_time:
remaining_foods = [i for i in range(food_count) if is_remaining[i]]
answer = remaining_foods[remaining_time % remaining_food_count] + 1
break
is_remaining[num] = False
remaining_food_count -= 1
remaining_time -= spent_time
prev_time = cur_time

return answer

## 토론

댓글을 입력하세요:
T H A U X

ps/problems/programmers/42891.txt · 마지막으로 수정됨: 2021/01/21 15:20 저자 teferi

### 문서 도구 