문제
풀이
1. 이중 for문 사용: 테스트 케이스만 성공
def solution(food_times, k):
answer = 0
times = 0 # 총 섭취 시간
# 네트워크 장애 후 먹을 음식이 남아있다면
if k < sum(food_times):
# 회전판이 얼마나 회전할 것인지
if sum(food_times) % len(food_times) == 0: # 나누어 떨어지면
how_many_turn = sum(food_times) // len(food_times)
else:
how_many_turn = sum(food_times) // len(food_times) + 1
# 음식을 다 먹을 동안
for _ in range(how_many_turn):
# 회전판이 한바퀴 돌 동안
for i in range(len(food_times)):
# 이미 다 먹은 음식이면
if food_times[i] == 0:
continue
# 음식이 남아있다면
food_times[i] -= 1 # i번 음식을 1만큼 섭취
times += 1 # 총 시간이 1초 증가
if k == times: # 네트워크 장애가 발생하면
answer = (i + 2) % len(food_times)
else: # 네트워크 장애 후 먹을 음식이 남아있지 않다면
answer = -1
return answer: 테스트 케이스는 성공. 그러나 정확성 테스트는 반절 틀리고, 효율성 테스트는 전부 시간 초과!
뭐가 문제일까.. 뭘 수정해야 할까?🤔
2. while 사용: 정확성 테스트 성공, 효율성 테스트 실패
def solution(food_times, k):
answer = 0
now_eat = 0 # 지금 먹을 음식의 index
times = 0 # 총 섭취 시간
# 네트워크 장애 후 먹을 음식이 남아있다면
if k < sum(food_times):
while True:
# 지금 먹을 음식이 남아있지 않다면, 다음 음식으로 넘어감
if food_times[now_eat] == 0:
now_eat = (now_eat + 1) % len(food_times)
continue
if k == times: # 네트워크 장애가 발생하면
answer = now_eat + 1 # index 이기에 +1 해야함
break
food_times[now_eat] -= 1 # 음식을 1만큼 섭취
times += 1 # 시간이 1초 증가
# 다음 음식 index
now_eat = (now_eat + 1) % len(food_times)
else: # 네트워크 장애 후 먹을 음식이 남아있지 않다면
answer = -1
return answer: 정확성 테스트는 통과, 효율성 테스트는 전부 시간 초과!
- 정확성 테스트에서 가장 많은 시간 복잡도를 보인 케이스
:테스트 27 〉 통과 (57.64ms, 10.1MB)
: 느리다ㅠ
3. 한 바퀴당 섭취 시간으로 풀이: 실패
def solution(food_times, k):
answer = 0
sum_food_times = 0 # 총 섭취 시간 0으로 초기화
remain_food_times = len(food_times) # 음식 개수
restart_food = 0 # 장애 복구 후 먹을 음식의 순서
now_index = 0 # 남은 음식의 index를 0으로 초기화
# 네트워크 장애 후 먹을 음식이 남아있다면
if k < sum(food_times):
# 한 바퀴씩 섭취 시간을 계산
for i in range(1, max(food_times)):
# i - 1번 회전까지 섭취 시간 < 네트워크 장애 발생 시간 < i번 회전까지 섭취 시간
if sum_food_times <= k < sum_food_times + remain_food_times:
# 장애 복구 후 몇 번째 음식을 먹어야 하는지 계산
restart_food = k - sum_food_times
for j in range(len(food_times)):
# 장애 복구 후 먹을 순서일 때
if now_index == restart_food:
answer = j + 1
break
elif food_times[j] >= i: # 장애 복구 후 남은 음식일 때
now_index += 1 # 남은 음식 중 순서 증가
# 총 섭취 시간 갱신 = (i - 1)번째까지 섭취 시간 + i번째 섭취 시간
sum_food_times += remain_food_times
# i번째 회전한 이후, 남는 음식 list
remain_food_times -= food_times.count(i)
else: # 네트워크 장애 후 먹을 음식이 남아있지 않다면
answer = -1
return answer: 테스트 케이스 실패, 정확성 테스트 반절 실패, 효율성 테스트는 다 실패.
if sum_food_times <= k < sum_food_times + remain_food_times:이 작동을 안한다..why..?
4. for문: 정확성 테스트 성공, 효율성 테스트 실패
def solution(food_times, k):
answer = 0
sum_food_times = [0] * (max(food_times) + 1) # 총 섭취 시간 list 0으로 초기화
now_food_times = len(food_times) # 현재 회전판의 섭취 시간
restart_food = 0 # 장애 복구 후 먹을 음식의 index
now_index = 0 # 남은 음식의 index를 0으로 초기화
now_rotation = 0 # 현재 회전 회수를 0으로 초기화
# 장애 복구 후 먹을 음식이 남아있을 때
if k < sum(food_times):
# a번째 회전 시 총 섭취 시간 list 생성
for a in range(1, max(food_times) + 1):
# a번째 회전의 총 섭취 시간
# = a - 1번째 회전의 총 섭취 시간 + a번째 회전의 섭취 시간
sum_food_times[a] = sum_food_times[a - 1] + now_food_times
# 현재 회전판의 섭취 시간 = 이전 회전판의 섭취 시간 - a의 개수
now_food_times -= food_times.count(a)
# 시간 복잡도를 줄이기 위해..
if k < sum_food_times[a]:
break
for b in range(1, max(food_times) + 1):
# 네트워크 장애 발생 시간을 넘은 경우
if k < sum_food_times[b]:
# 장애 복구 후 먹을 음식의 순서 = 이전 회전까지 다 먹고, 남은 순서
restart_food = k - sum_food_times[b - 1]
now_rotation = b # 현재 b번째 회전판
break
# 전체 food_times list를 살펴보며
for c in range(len(food_times)):
# 더 먹을 수 있는 음식일 때
if food_times[c] >= now_rotation:
# 장애 복구 후 먹을 순서일 때
if now_index == restart_food:
answer = c + 1
break
else:
now_index += 1 # 남은 음식의 순서 증가
else: # 장애 복구 후 먹을 음식이 남아있지 않을 때
answer = -1
return answer: 정확성 테스트는 통과, 효율성 테스트는 전부 시간 초과!
- 정확성 테스트에서 가장 많은 시간 복잡도를 보인 케이스
:테스트 27 〉 통과 (3.38ms, 10.2MB)
: 2번 while 사용때보다 훠어어얼씬 빨라졌다!
근데 왜.. 여전히 효율성 테스트는 통과 못하는거지..ㅠㅜ
5. 우선순위 큐 사용: 성공!
import heapq
def solution(food_times, k):
food_times_cv = sorted(food_times[:], reverse = True) # list 복사해서 거꾸로 정렬
q = [] # 우선순위 큐를 담을 list 초기화
now_times = 0 # 이번 단계 섭취 시간을 0으로 초기화
previous_times = 0 # 이전 음식의 총 섭취 시간 0으로 초기화
result = [] # 결과를 담을 list 초기화
# 모든 음식을 다 먹은 후에 네트워크 장애가 발생하면
if k >= sum(food_times):
return -1
# 모든 음식을 다 먹기 전에 네트워크 장애가 발생하면
for i in range(len(food_times)):
# 음식 시간, 음식 번호 순서대로 우선순위 큐에 넣음
heapq.heappush(q, (food_times[i], i + 1))
while True:
'''
각 단계마다 가장 섭취 시간이 적은 음식을 하나씩 먹어치움
근데 이전 음식을 다 먹는 과정에서 현재 음식도 일정량 먹게됨
즉, 이번 단계 섭취 시간
= (현재 음식의 총 섭취 시간 - 이전 음식의 총 섭취 시간) * 남은 음식들 list의 길이
'''
now_times = (food_times_cv[-1] - previous_times) * len(food_times_cv)
# 이번 단계 섭취 시간이 네트워크 장애까지 남은 시간보다 작을 때
# 즉, 현재 음식을 다 섭취해도 네트워크 장애 발생 전일 때
# 다음 음식으로 넘어가야 함(변수들 갱신)
if now_times < k:
k = k - now_times # 남은 섭취 시간 갱신
previous_times = food_times_cv[-1] # 현재 음식이 이전 음식으로 갱신됨
food_times_cv.pop() # 가장 적은 섭취 시간의 음식을 list에서 제거
heapq.heappop(q) # 가장 적은 섭취 시간의 음식을 우선순위 큐에서 제거
# 이번 단계 섭취 시간이 네트워크 장애가 발생하는 시간과 같거나 넘어설 때
# 즉, 현재 음식을 다 섭취하게 되면 네트워크 장애 발생 이후일 때
# 따라서 현재 음식은 다 섭취하지 않고, 번호순 정렬해서 하나씩 세어보자
else:
# 음식 번호 기준으로 우선순위 큐를 정렬하여 result로 지정
result = sorted(q, key = lambda x: x[1])
# 장애 복구 이후 먹어야 할 음식 번호 반환
return result[k % len(food_times_cv)][1]'''
각 단계마다 가장 섭취 시간이 적은 음식을 하나씩 먹어치움
근데 이전 음식을 다 먹는 과정에서 현재 음식도 일정량 먹게됨
즉, 이번 단계 섭취 시간
= (현재 음식의 총 섭취 시간 - 이전 음식의 총 섭취 시간) * 남은 음식들 list의 길이
'''
now_times = (food_times_cv[-1] - previous_times) * len(food_times_cv): 이 부분 때문에 그동안 실패였던 것..! 그니까 매번 가장 시간이 적은 음식을 먹게 되면, 그 다음으로 시간이 적은 음식을 먹을때는 그전에 먹은 음식의 총 시간 만큼을 빼주어야 한다!
- 정확성 테스트에서 가장 시간 복잡도가 높은 케이스
테스트 26 〉 통과 (1.62ms, 10.5MB) - 효율성 테스트에서 가장 시간 복잡도가 높은 케이스
:테스트 3 〉 통과 (443.86ms, 39.9MB)
다른 사람 풀이
1. jifrozen님: 이런 방법이?!(itemgetter)
https://velog.io/@jifrozen/Algorithm-무지의-먹방-라이브-그리디
from operator import itemgetter
def solution(food_times, k):
foods = []
for i in range(len(food_times)):
foods.append([food_times[i], i])
foods.sort()
pretime = 0
n = len(food_times)
for i in range(len(food_times)):
time = foods[i][0] - pretime
if time != 0:
spend = time * n
if spend <= k:
k -= spend
pretime = foods[i][0]
else:
k %= n
sublist = sorted(foods[i:], key=itemgetter(1))
return sublist[k][1] + 1
n -= 1
return -1itemgetter?
: sorted(foods[i:], key=lambda x: x[1])
내 인생의 주연