우선 처음 생각났던 풀이방법은 큐 자료구조에 집어넣고 순차적으로 시뮬레이션을 돌려보는 것이었다. 그러나 조건에 의해서 시간복잡도에 걸린다.
두번째로 생각해낸 방법은 각 음식들이 있는 접시에서 먹는데 적은 시간이 드는 순으로(오름차순)으로 정렬하는 것이었다.
이렇게 정렬을 하게 되면 시뮬레이션으로 하나씩 섭취시간을 빼는 것이아니라 k값에 가까이 갈때까지 가로*세로형태의 직사각형 양 만큼의 섭취시간을 한번에 상수시간으로 빼버릴 수 있다.
즉 k근처 갈때까지는 일일이 카운트하지말고 곱하기를 통해서 한번에 제외시켜버릴 수 있다.
설명이 난잡하니 나중에 복습하면서 깔끔하게 정리해야지
최종코드
'''
회전판 n개의 음식(1 ~ n)
각 음식마다 섭취시간 소모값이있음
일단 순차탐색은 절대안됨 -> k값때문에..
바로 떠오르는 생각은 막대그래프 그려서 자르기 -> 상수시간으로 잘라버리기
'''
def solution(food_times, k):
# 더 섭취할 음식이 없는 경우
total = sum(food_times)
if total <= k: return -1
# index번호와 함께 저장
s = []
for i, x in enumerate(food_times):
s.append((i+1, x))
s.sort(key = lambda x : x[1])
n = len(s)
std, pre = 0, 0
ans_i = 0
for i in range(n):
pre += abs(std-s[i][1]) * n
if pre >= k:
ans_i = i
pre -= abs(std-s[i][1]) * n
break
std = s[i][1]
n -= 1
#print(std, ans_i)
#print("현재까지 먹은 정도 :", pre)
# 남은 음식들을 담은 리스트
new_s = s[ans_i:]
new_s.sort()
index = (k - pre) % len(new_s)
return new_s[index][0]
-> 사실 머리속에서 떠오른것을 거의 바로 프로그래밍한거라 코드가 깔끔하진 않지만.. 일단 아이디어생각은 금방 들었고 구현하는데에 스스로 헷갈려서 실수했던 부분을 빼면 나름 1시간정도에 풀었던 것 같다. 후 실전이면 조금더 느렸을 지도?!
