(수정 전 풀이)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | def solution(ft, k): c = 0; sum = 0; food_size = len(ft); for i in ft: sum += i; k += 1; i = 0; if sum < k: return -1; rt = [0 for i in ft]; while c < k: # 모든걸 다 셀 때까지 t = i % food_size; if rt[t] < ft[t]: rt[t] += 1; c += 1; i += 1; return t + 1; | cs |
정확성 테스트는 통과했는데, 효율성 테스트를 통과하질 못했다.
O(k)일텐데 통과하지 못하는걸 보니 O(1)에 가깝게 짜야하는건데 방법을 못 찾겠어서 해답을 봤다.
(수정 후 풀이)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | import heapq; foodlist = []; def solution(foods, k): foodidx = 0; ate = 0; s = 0; #먹기위해 쓴 시간 prev = 0; #이전에 먹은 시간 size = len(foods); count = 0; for i in foods: heapq.heappush(foodlist, (i,foodidx + 1)); foodidx += 1; if k >= sum(foods): return -1; # 이전에 계산했던 합 + 남은 먹여야할 용량 * 남은 갯수 이 k를 안 넘을 때까지 # 즉 현재 계산하는 단계 에서 시간이 넘치는지... while s + (foodlist[0][0] - prev) * size <= k : now = heapq.heappop(foodlist)[0]; # 남은 먹어야할 용량 * 남은 갯수 s += (now - prev) * size; # 다 먹은걸로 처리하므로 갯수 제거 size -= 1; # 다음 단계 계산에서 활용 가능하도록 넣어두기 prev = now; count += 1; # (시간 - 이전까지의 합) % 남은갯수 를 하면 현재 단계에서의 적절한 위치를 찾음 result = sorted(foodlist,key= lambda x: x[1]); return result[(k - s) % size][1] print(solution([3,1,1,3], 7)); | cs |
여기서의 포인트는 아래와 같다.
시간 순대로 1씩 먹어가면서 진행하기 때문에,
예를 들어 N만큼 해당하는 음식들을 다 먹었다면, 그를 넘는 음식들도 N만큼은 먹었다는 것이다.
즉, 잔여시간을 그만큼 한번에 줄여놓을 수 있다.
이걸 작은 무게부터 진행하면 된다, 큰 무게는 항상 작은 무게를 포함하니 한꺼번에 잘라내갈 수 있으니까....
본인은 다른분 해설을 보고 한번에 이해가 안 갔던게, 얼만큼 계산양이 주며 그 과정이 어떤지를 이해를 못했었다.
아래 그림을 보면 녹색과 붉은색으로 표기해 놓은 부분이 각 단계별 계산법이다.
현재 단계에서 필요한 시간 = (잔여용량 * 잔여 갯수)
현재 단계에서 필요한 시간이 남은 시간보다 클 때 가 넘치는 부분이므로 이 때를 기준으로 음식 순서를 센다.
위 그림에선 녹색일 때 넘치는 부분이므로, 이 때 원래 시간에 걸리는 부분을 찾으면 된다.
잔여시간(코드상에서는 시간 - 이전까지의 합) 을 잔여 갯수로 나눈 나머지가 해당 음식이므로, 음식의 원래 index를 반환하면 된다.
참고로 기존 해법과 신규 해법의 연산 횟수의 차이는 아래를 그림을 통해 알 수 있다.
이걸 원래는 말로만 이해하거나 설명하고 싶었는데 능력 부족 ㅠㅠ
덧글