문제 설명
효율성 테스트에 부분 점수가 있는 문제입니다.
평소 식욕이 왕성한 무지는 자신의 재능을 뽐내고 싶어 졌고 고민 끝에 카카오 TV 라이브로 방송을 하기로 마음먹었다.
그냥 먹방을 하면 다른 방송과 차별성이 없기 때문에 무지는 아래와 같이 독특한 방식을 생각해냈다.
회전판에 먹어야 할 N 개의 음식이 있다.각 음식에는 1부터 N 까지 번호가 붙어있으며, 각 음식을 섭취하는데 일정 시간이 소요된다.무지는 다음과 같은 방법으로 음식을 섭취한다.
- 무지는 1번 음식부터 먹기 시작하며, 회전판은 번호가 증가하는 순서대로 음식을 무지 앞으로 가져다 놓는다.
- 마지막 번호의 음식을 섭취한 후에는 회전판에 의해 다시 1번 음식이 무지 앞으로 온다.
- 무지는 음식 하나를 1초 동안 섭취한 후 남은 음식은 그대로 두고, 다음 음식을 섭취한다.
- 다음 음식이란, 아직 남은 음식 중 다음으로 섭취해야 할 가장 가까운 번호의 음식을 말한다.
- 회전판이 다음 음식을 무지 앞으로 가져오는데 걸리는 시간은 없다고 가정한다.
무지가 먹방을 시작한 지 K 초 후에 네트워크 장애로 인해 방송이 잠시 중단되었다.무지는 네트워크 정상화 후 다시 방송을 이어갈 때, 몇 번 음식부터 섭취해야 하는지를 알고자 한다.각 음식을 모두 먹는데 필요한 시간이 담겨있는 배열 food_times, 네트워크 장애가 발생한 시간 K 초가 매개변수로 주어질 때 몇 번 음식부터 다시 섭취하면 되는지 return 하도록 solution 함수를 완성하라.
제한사항
- food_times 는 각 음식을 모두 먹는데 필요한 시간이 음식의 번호 순서대로 들어있는 배열이다.
- k 는 방송이 중단된 시간을 나타낸다.
- 만약 더 섭취해야 할 음식이 없다면
1을 반환하면 된다.
정확성 테스트 제한 사항
- food_times 의 길이는
1이상2,000이하이다. - food_times 의 원소는
1이상1,000이하의 자연수이다. - k는
1이상2,000,000이하의 자연수이다.
효율성 테스트 제한 사항
- food_times 의 길이는
1이상200,000이하이다. - food_times 의 원소는
1이상100,000,000이하의 자연수이다. - k는
1이상2 x 10^13이하의 자연수이다.
전체 코드
import heapq
def solution(food, k):
answer = 0
sums=0
food_times=[]
for i in range(len(food)):
#(식사 소요 시간, 인덱스)
sums+=food[i]
heapq.heappush(food_times,(food[i],i+1))
#전체 음식을 먹는 시간보다 방송 종료 시간이 나중이라면, 더 먹을게 없으므로 -1리턴
if sums<=k:
return -1
#소요 시간
time=0
#이전 음식
previous=0
#남은 음식들의 수
food_count=len(food_times)
#현재 식사를 마치기 위해 걸리는 시간을 구한다.
#걸리는 시간= (현재 식사시간과 바로 이전 식사시간의 차이)*남은 음식들의 수
#현재까지 걸린 소요 시간 + 현재 음식을 먹는데 걸리는 시간 >k이면 반복 종료.
while time+(food_times[0][0]-previous)*food_count<=k:
#한 사이클이 끝난 후, 가장 작은 것 빼내기
now=heapq.heappop(food_times)[0]
#현재 까지 걸린 시간 누적
time+=(now-previous)*food_count
#남은 음식수를 줄이기
food_count-=1
#이전 음식 갱신
previous=now
#음식 번호 순으로 정렬 (우선순위 큐는 루트가 최소 또는 최대임을 보장할 뿐, 순서는 보장하지 않는다. 따라서 나머지 먹을 순서에 대해 구할 땐 음식 번호순으로 정렬해줄 필요가 있다.)
sorted_by_order=sorted(food_times,key=lambda x:x[1])
#남은 소요 시간
surplus=k-time
remainder=surplus%len(sorted_by_order)
return sorted_by_order[remainder][1]해설
예를 들어 [1,3,2,3,5,6]이라는 입력이 들어왔다고 하자.
이에 대해 시뮬레이션해보자.
6초가 지나면 [0,2,1,2,4,5]가 된다. 11초가 지나면 [0,1,0,1,3,4]가 된다.
그런데 이렇게 할 경우 0으로 지워진 원소를 '배열'에서 빼내는 것과 다른 수들을 -1씩 감소 시켜야 한다는 점에서 시간 복잡도가 크다. ( '배열'에서 원소 한 개 삭제는 O(n)다.)
만약 빼내지 않고 순회해본다 하더라도 효율성 테스트에선 100,000,000이나 되는 원소에 k는 2 x 10^13이나 된다.
대략 k // 전체 원소 개수만큼 소요되기 때문에 엄청난 시간이 소요된다.
즉, k가 엄청나게 크고 전체 원소 개수가 매우 작다면 O(10^13)만큼 배열을 순회해야 하므로 실패처리 된다.
따라서 위 두가지 방법말고 다른 방법이 필요하다. (참고로 덱을 이용해서 푼다하더라도 단순 순회한 것과 같은 시간복잡도를 가진다. 따라서 덱을 이용한 풀이도 안된다.)
다른 해설을 참고한 풀이는 다음과 같다.
먼저 (식사 시간, 인덱스+1)의 튜플로 정리해서 최소 힙에 담자.
위 입력의 경우 [(1,1), ~~~ ]이 될 것이다. 최소 힙이기 때문에 루트가 최소임을 보장하지만, 그 이후의 순서는 보장되지 않는다.
힙의 루트인 (1,1)에 대해 식사를 마치려면 1*6(음식 개수)=6초만큼 걸린다.
(1,1)에 대한 처리가 끝나면 힙에서 (1,1)을 빼내고 힙은 [(2,3), ~~~]과 같이 된다.
이 (2,3)에 대해 식사를 전부 마치려면 6초 + (2-1)*5 =11초이다. 여기서 5는 음식 개수이다. 그리고 (2-1)은 현재 힙의 루트- 힙의 이전 루트이다. 이렇게 처리한 이유는 6초가 걸리면 1은 0이 되고 2는 1이 되기 때문이다. 이 때 두 수의 차이는 1이다.
(2,3)을 빼내면 힙은 [(3,2) , ~~~]가 될 것이다. (3,2)에 대해 식사를 마치려면 11+ (3-2)*4=11+4=15초가 되야 한다.
(3,2)를 빼내면 힙은 [(3,4) , ~~~]가 된다. (3,4)에 대해 식사를 마치려면 6+5+4+ (3-3)*3=15가 된다.
이렇게 된 이유는 현재 힙 루트와 힙의 이전 루트가 같기 때문이다. 즉, (3,2)에 대해 식사를 마치는 바퀴에서는 자동으로 (3,4)에 대한 식사도 마치게 된다. 따라서 힙이 바로 [(5,5),~~]가 된다.
그런데 예를 들어 k=13일 경우 어디부터 시작해야 할까?
일단, k=11이면 (2,3)에 대한 식사가 끝난 시점이다. 그렇다면 힙을 다시 인덱스 순으로 정렬하면
[(3,2),(3,4),(5,5),(6,6)]이 될 것이다. k=11일 경우 (3,2), k=12일 경우 (3,4), k=13일 경우 (5,5)를 먹을 차례가 될 것이다.
즉, 나머지 처리에 대해서는 인덱스 순으로 오름차순 정렬하여 세보면 된다. (나머지 연산자를 활용하면 훨씬 효율적으로 계산할 수 있다.)
이를 일반화하면 다음과 같다.
-
현재 소요 시간 +(힙의 루트 (식사 소요 시간이 최소 인 것) - 이전 식사 소요 시간 )*남은 음식 수를 구한다. 이 시간이 k를 넘어서면 반복을 종료한다.
1-1.한 바퀴가 끝난 후 가장 작은 것, 즉 최소 힙의 루트를 heappop한다. O(log N)
1-2.현재 소요시간을 누적한다.
1-3.남은 음식 수를 하나 줄이고, 이전에 먹었던 음식을 방금 힙에서 꺼낸 것으로 갱신한다.
-
인덱스 순으로 정렬한 후, 나머지 연산자를 이용해 나머지 처리를 한다.
이 방식이 더 효율적인 이유는 아래 예를 보면 알 수 있다.
food_times = [2억 6, 2억 8, 2억 1]이고 k=2억 5이라고 하자.
단순 순회인 경우에는 인덱스 커서가 0,1,2,0,1,2,...의 순서로 2억 5번 옮겨져야 한다.
반면, 해설 풀이의 경우 첫 번째 식사 소요 시간에 대해 2억 1초가 바로 계산된다.
그리고 남은 시간이 4초이고 남은 식사가 2개이므로 소요 시간 순서대로 표현하면 2억 6, 2억 8 , 2억 6, 2억 8이다.
따라서 2억 8초가 걸리는 식사 시간의 인덱스인 2(1+1)을 리턴하면 된다.
이와 같이 k또는 food_times의 원소의 값이 클수록 해설 풀이가 훨씬 효율적이다.
다시 풀기 1회차
import heapq
def solution(food_times, k):
heap=[]
for i,food in enumerate(food_times):
heapq.heappush(heap,(food,i+1))
# 바로 이전 값
previous=0
while heap:
food_value,food_index=heap[0]
# 1바퀴를 채울 수 없다면, 종료
if (food_value-previous)*len(heap)>k:
break
k-=(food_value-previous)*len(heap)
previous=food_value
heapq.heappop(heap)
#힙에서 남은 것들을 인덱스 순으로 정렬
remainder_of_heap=sorted(heap,key=lambda x:x[1])
if len(remainder_of_heap):
return remainder_of_heap[k%len(remainder_of_heap)][1]
else:
return -1
