본인은 크게 while 문으로 돌려서 종료 지점과 food_times의 인덱스 값이 0인 경우의 if 문 + while 문을 돌려서 네트워크 에러 발생 시 인덱스 위치 값을 반환하도록 하였다.
아마 2중 반복문을 사용해서 시간복잡도가 O(N^2)이기에 효율성 부분에서 문제가 있다고 생각한다. < 해결한 방법 > 다른 분들의 해설을 참고하였더니 그리드 알고리즘 즉, 최선의 방법을 택해서 해결하는 방법으로 접근하였다. heapq를 이용해서 음식 섭취 시간이 짧은 음식부터 해결해서 주어진 시간 k를 감소시켜나가는 방법으로 했다.
1. 모든 음식의 정보 -> (음식 섭취 시간, 음식의 넘버)를 heap에 삽입한다. -> 섭취 시간이 가장 짧은 데이터가 앞에 정렬됨. 2. heap[0]번째의 음식 섭취 시간을 계산한다. (이전의 섭취 시간을 현재의 섭취 시간에서 빼줘야 한다) 3. 푸드 리스트의 개수를 -1 하고, k 값도 (섭취 시간 * lens) 만큼 빼준다. previous 이전의 음식 섭취 시간을 갱신한다. 4. 더 이상 k를 빼줄 수 없을 때, 음식 넘버를 기준으로 sort 하고 (k * len) 를 해주면 몇 번째 음식 넘버인지 값이 나온다. 역시 카카오 문제 답게 아이디어 떠오르기가 쉽지 않았다. 처음에는 무식하게 처리했다가 효율성에서 광탈하였는데, 그리디 알고리즘으로 접근을 하는 것을 알더라도 완벽하게 아이디어가 해결되지도 않았고 값 처리하는데 있어서도 많이 헤맸다..... 확실히 더 많이 풀어봐야할 것 같다.
2. 정답코드
(1) 효율성 실패 코드
def solution(food_times, k):
answer = 0
time = 0
idx = 0
while True:
# 종료
if time > k:
break
# idx 초기화
if idx >= len(food_times):
idx = 0
# 0 방지
if food_times[idx] == 0:
while True:
if food_times[idx] != 0:
break
idx += 1
if idx >= len(food_times):
idx = 0
food_times[idx] -= 1
idx += 1
time += 1
answer = idx
return answer
(2) 해결한 코드
def solution(food_times, k):
import heapq
answer = -1
heap = []
for i in range(len(food_times)):
heapq.heappush(heap, (food_times[i], i + 1))
lens = len(food_times)
previous = 0
while heap:
food_time = (heap[0][0] - previous) * lens
print(heap, food_time)
if k >= food_time:
k -= food_time
lens -= 1
previous, _ = heapq.heappop(heap)
else:
result = sorted(heap, key=lambda x : x[1])
answer = result[k % lens][1]
break
return answer
