Q06. 무지의 먹방 라이브 (2019 카카오 기출)
코딩테스트 연습 - 무지의 먹방 라이브 | 프로그래머스 (programmers.co.kr)
코딩테스트 연습 - 무지의 먹방 라이브
programmers.co.kr
ㅋㅋㅋ 아.. 처음엔 쉽네 쉬워~ 하고 코드를 간단하게 짰는데
def solution(food_times, k):
current_eating_food = 0
foodnum = len(food_times)
for _ in range(k):
while food_times[current_eating_food] == 0:
current_eating_food = (current_eating_food + 1) % foodnum
food_times[current_eating_food] -= 1
current_eating_food = (current_eating_food + 1) % foodnum
return current_eating_food + 1
ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 처참한 결과
효율성은 고사하고 일단 왜틀렸는지 모르겠다... 뭐지
아 알았다!!!
def solution(food_times, k):
current_eating_food = 0
foodnum = len(food_times)
for _ in range(k):
food_times[current_eating_food] -= 1
current_eating_food = (current_eating_food + 1) % foodnum
while food_times[current_eating_food] == 0:
current_eating_food = (current_eating_food + 1) % foodnum
return current_eating_food + 1
굵은 글씨 친 부분을 이렇게 뒤로 옮겨야돼! 왜냐하면 마지막 iteration 때
current_eating_food = (current_eating_food + 1) % foodnum
를 수행했는데 current_eating_food가 가리키는 음식이 이미 다 먹은음식(0)이면 안되니까!!!
하ㅎㅏ..ㅋㅋㅋㅋㅋㅋㅋㅋ
하지만 너무 naive한 알고리즘으로 인해 시간초과가 뜨는 모습..ㅠㅠ
시간효율성을 어떻게 올릴 수 있을까!!?!?!
하고 고민해봤더니 잠깐만.. 내가 하나 실수한게 있는데?
- 만약 더 섭취해야 할 음식이 없다면 -1을 반환하면 된다.
내가 짠 코드는 iteration 중에 음식을 다먹으면 무한루프에 빠진다. 그래서 시간초과가 떴구나ㅎ..
음식을 다 먹었는지 체크할 수 있어야되겠다.
def solution(food_times, k):
current_eating_food = 0
foodnum = len(food_times)
for _ in range(k):
food_times[current_eating_food] -= 1
current_eating_food = (current_eating_food + 1) % foodnum
start_point = current_eating_food
while food_times[current_eating_food] == 0:
current_eating_food = (current_eating_food + 1) % foodnum
if current_eating_food == start_point:
return -1
return current_eating_food + 1
오케이~ 정확성은 맞췄다. 정답!!
이제 효율성 측면으로 들어가야된다.
일단 제한사항을 잘 살펴보자
효율성 테스트 제한 사항
- food_times 의 길이는 1 이상 200,000 이하이다.
- food_times 의 원소는 1 이상 100,000,000 이하의 자연수이다.
- k는 1 이상 2 x 10^13 이하의 자연수이다.
걍 대충 요약하면 food_times 가 엄청 길고(음식이 엄청 많고)
food_times 원소들의 크기도 엄청크고
k도 엄청 클 때도 동작해야 된다는 거다.
이건 그냥 feel인데 왠지 나눗셈과 나머지 연산으로 뭔가 지지고 볶을거같은 느낌..
일단 타이머를 20분 맞춰놓고 고민을 해보자. 고민해보고 안되면 정답지 봐야지.
극단적으로 다음과 같은 케이스를 생각해보면
[100,100,101] k=300
일일이 k번의 iteration을 수행하면서 food를 먹어야될까? 아니다.
food 개수가 3개고 최소 100씩은 있으니까 3*100 = 300번의 iteration은 스킵하고 각 리스트에서 100씩 빼도 된다.
[0,0,1]
이 아이디어를 기반으로 최적화를 해보고싶다.
즉 food_times 중에 min 값을 찾아서 그걸 food개수랑 곱하면 (위의 경우 100*3) 그만큼의 iteration을 한번에 스킵할 수 있다는 것이다.
그리고 효율적으로 짜려면 (음식번호, 음식 양) 이렇게 쌍을 묶어서 관리하는게 좋을듯하다. 다 먹은 음식은 리스트에서 빼버리게. 그래야 남은 음식 개수를 구하기가 수월하다.
-----여기까지 생각하고 정답지를 봤다.------
정답지는 이 food_times min값을 찾는 것을 min heap으로 구현했다. 힙은 직접 구현하긴 좀 까다로운 면이 있어서 라이브러리 사용법을 이번참에 익혀두는 것이 좋겠다고 생각이든다. 아예 나중에 알고리즘 테스트에 유용한 라이브러리 싹 정리하는 것도 좋을수도 있겠네.
이 min값을 남은 food 개수랑 곱해보고 k보다 작으면 딱 빼버리고
min값이 k보다 크면 남은 음식들 중에 k초 후에 없어질 음식은 없으니 그냥 쭉 나열해서 k번째 음식을 출력하면 된다. (나머지 연산 쓰면 간편)
아래 코드가 책 저자분의 소스코드
import heapq
def solution(food_times, k):
if sum(food_times) <= k:
return -1
q = []
for i in range(len(food_times)):
heapq.heappush(q, (food_times[i], i+1))
sum_value = 0
previous = 0
length = len(food_times)
while sum_value + ((q[0][0] - previous) * length) <= k:
now = heapq.heappop(q)[0]
sum_value += (now - previous) * length
length -= 1
previous = now
result = sorted(q, key=lambda x:x[1])
return result[(k - sum_value) % length][1]
아 어렵다..ㅋㅋ
일단 heapq 사용법
푸시 heapq.heappush(리스트, 원소)
팝 heapq.heappop(리스트)
기본적으로 minheap인듯?
그리고 원소가 튜플같은 iterable인경우 맨 앞 요소를 기준으로 heap이 구성된다고함.
리스트를 베이스로 하는거니까 루트노드는 리스트[0]으로 참조하면 될거고.
maxheap을 쓰고싶으면 원소값을 반전시켜서 넣어야될듯함!
sum_value는 여태 먹은 음식 양인거 같고
length는 남은 음식 개수인듯하다.
previous는 가장 최근에 먹어치운 음식의 양? 뭐라고 표현해야되지. [100,100,101]에서 300을 먹어서 [0, 0, 1]이 되었으면 previous는 100일것이다. 그러니까 min값을 저장한거라고 보면 될듯. 이걸 왜 두냐면 저자는 내가 위에서 naive하게 구현했을 때처럼 직접 리스트 원소의 값을 줄여가며 계산하고싶지 않은것이다. 인풋은 그대로 보존하고 싶고 실제로 그렇게하는게 더 효율적이기도 하니까 이렇게 하는 것 같다. 남은 음식중에 min값 - previous하면 그 음식의 남은 양을 구할 수 있다. [100,100,101]의 예에서 300을 먹어치우고 나면 100인 음식은 사라져서 [101]만 남는거고 previous가 100이니까 이 음식의 남은 양은 101-100=1이되는 것. 근데 이게 지금은 이해되는데 내가 나중에 이 글을 다시 봤을 때 또 이해할 수 있을련지는 모르겠다;;ㅋㅋㅋㅋ
((q[0][0] - previous) * length) 혹은 (now - previous) * length 이건 남은 음식중에 제일 양이 적게남은 음식의 양 * 남은 음식의 개수이다. [100,100,101]의 예에서 100*3이라고 보면 된다.
이 코드가 참 영리하다고 생각한 포인트는
1. sort하는 부분. 어차피 sum_value + (min값 * length)가 k보다 커져서 루프가 끝나버리면 남은 음식들은 k초 후에 사라질 일이 없으니 그냥 번호순으로 정렬한다음에 나머지 연산으로 k번째 음식이 뭐가 될건지 판단하는거
2. 저 반복문의 로직은 음식의 양이 같은 음식들이 여러개 있어도 오류없이 동작한다는거. 예를 들어 [10,10,10,10,15] 이렇게 양이 같은 음식들이 여러개 있어도 정확하게 잘 돌아간다.
혼자 짜라고 하면 절대 못짤거같다 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
일단 운동다녀오자