2018년 카카오 blind 코딩 테스트 - 무지의 먹방 라이브 python

2018년 카카오 blind 코딩 테스트 -  무지의 먹방 라이브 python

문제 설명 : 무지의 먹방 라이브 : Greedy 무지의 먹방 라이브 * 효율성 테스트에 부분 점수가 있는 문제입니다. 평소 식욕이 왕성한 무지는 자신의 재능을 뽐내고 싶어 졌고 고민 끝에 카카오 TV 라이브로 방송을 하기로 마음먹었다. 그냥 먹방을 하면 다른 방송과 차별성이 없기 때문에 무지는 아래와 같이 독특한 방식을 생각해냈다. 회전판에 먹어야 할 N 개의 음식이 있다. 각 음식에는 1부터 N 까지 번호가 붙어있으며, 각 음식을 섭취하는데 일정 시간이 소요된다. 무지는 다음과 같은 방법으로 음식을 섭취한다. 무지는 1번 음식부터 먹기 시작하며, 회전판은 번호가 증가하는 순서대로 음식을 무지 앞으로 가져다 놓는다. 마지막 번호의 음식을 섭취한 후에는 회전판에 의해 다시 1번 음식이 무지 앞으로 온다. 무지는 음식 하나를 1초 동안 섭취한 후 남은 음식은 그대로 두고, 다음 음식을 섭취한다. 다음 음식이란, 아직 남은 음식 중 다음으로 섭취해야 할 가장 가까운 번호의 음식을 말한다. 회전판이 다음 음식을 무지 앞으로 가져오는데 걸리는 시간은 없다고 가정한다. 무지가 먹방을 시작한 지 K 초 후에 네트워크 장애로 인해 방송이 잠시 중단되었다. 무지는 네트워크 정상화 후 다시 방송을 이어갈 때, 몇 번 음식부터 섭취해야 하는지를 알고자 한다. 각 음식을 모두 먹는데 필요한 시간이 담겨있는 배열 food_times, 네트워크 장애가 발생한 시간 K 초가 매개변수로 주어질 때 몇 번 음식부터 다시 섭취하면 되는지 return 하도록 solution 함수를 완성하라. 제한 사항 food_times 는 각 음식을 모두 먹는데 필요한 시간이 음식의 번호 순서대로 들어있는 배열이다. k 는 방송이 중단된 시간을 나타낸다. 만약 더 섭취해야 할 음식이 없다면 -1을 반환하면 된다. 정확성 테스트 제한 사항 food_times 의 길이는 1 이상 2,000 이하이다. food_times 의 원소는 1 이상 1,000 이하의 자연수이다. k는 1 이상 2,000,000 이하의 자연수이다. 효율성 테스트 제한 사항 food_times 의 길이는 1 이상 200,000 이하이다. food_times 의 원소는 1 이상 100,000,000 이하의 자연수이다. k는 1 이상 2 x 10^13 이하의 자연수이다.

출처 : https://programmers.co.kr/learn/courses/30/lessons/42891

문제 풀이

단순 무식한 방법으로 List를 k만큼 돌면서 각 원소 값을 -1로 줄이고, 0인 경우는 인덱스를 뛰어넘어가면서 검사하면서 최종 인덱스를 반환하는 방식으로 구현하면 효율성 검사에서 시간 초과하게 됩니다.

food_times [10, 4, 6]  k=17인 경우

빠르게 검색하는 방법은 food_times에서 오름 차순으로 정렬하여 제일 적은 시간이 먼저가게 배치하는 것입니다.

정렬을 하면 다음과 같이 되겠죠 -> food_times [4(#2), 6(#3), 10(#1)] 

k와 비교를 할 것인데 만약 제일 적은 시간(4)를 다 먹기 위해서 k가 몇 번을 돌아야 할까요?

전체 배열을 3바퀴를 돌아 4번을 먹어치우면 0 이됩니다. 그러면 k 는 4*3 = 12 만큼 움직였습니다.

일반화시키면 전체 원소 길이 length = len(food_times)와 제일 적은 시간 min_foods 라고 명명하면 k = length * min_foods 이겠죠?  - min_foods를 뽑는 방식을 생각해보면 우선순위 큐(Priority Queue)를 사용하여 값을 오름차순 정렬로 제일 작은 값을 빼내는 get()을 쓰면 되겠다가 생각하면 정말 좋겠죠 :D 이렇게 되면, 제일 적은 시간의 음식은 빠져나가게 되고 length는 하나 줄게 됩니다. length -= 1

자 그렇게 되면 남은 음식은 [6(#3), 10(#1)] 값을 업데이트 해보면 각기 4번 돌았으니깐 [2(#3), 6(#1)] 그리고 k 값을 업데이트 해보죠. 위에서 12번 썼으니 k=(17-12)=5이 됩니다.

위와 같이 또 적은 음식의 남은 시간 2초를 없애려면 2번 돌아야합니다.

2*2=4 입니다. 

자 지금의 과정을 풀어써봅시다. 현재 #3의 6에서 이전의 단계의 음식 #2의 4를 뺐습니다. 6-4 = 2 그리고 지금 현재의 배열의 길이인 length 2죠. 그래서 소모되는 k값은 2*2=4가 되었습니다.

즉 우리는 이전(빼버린) 음식의 시간 값을 기억해야 하고, 지금의 값과 비교할 것이며, 또한 전체 길이 food_times의 length 도 과일을 뺄 때마다 -1을 해줘야 한다는 풀이 과정이 생깁니다.

자 그래서 업데이트하면 [2(#1)] k =(5-4)1가 됩니다.

k가 남은 현재 시간보다 적기 때문에 위의 과정을 멈추고 풀어씁니다.

[2(#1)] -> [1(#1)] [1(#1)] 

여기서 k=1일 경우에 우리의 문제는 다음에 먹을 과일은 무엇인지 물어보기 때문에 원하는 위치의 값은 k+1이죠 

그래서 2번째인 #1을 정답으로 반환하면 됩니다.

여기서 푸는 방식은 값을 기준으로 오름차순으로 정렬되는 우선순위 큐(Priority Queue)를 사용합니다.

우선순위 큐는 일반적인 큐의 순서대로 원소를 제거하는 선입선출(FIFO) 방식이 아니라, 순서에 상관없이 추가가 되어도 값을 뽑을 때는 가장 작은값(오름차순)을 제거하는 특성을 지닌 자료 구조 입니다. 

from queue import PriorityQueue를 사용하면 됩니다. PriorityQueue에 데이터를 넣는 것은 put(), 뽑는 것은 get()을 사용할 것이고, 데이터를 넣을 때는 Tuple 형식으로 (정렬되는 기준 key 값, value값) 넣어주면 됩니다.

[1] 만약 더 섭취해야 할 음식이 없다면 -1을 반환합니다. 즉 k라는 시간이 food_times 전체 합보다 크거나 같으면 더 이상 먹을 음식이 없습니다.

[2] 다음으로는 우선순위 큐에다가 (food_times의 음식 먹는데 필요한 시간, 음식 index)를 추가합니다.

[3] 위의 과정처럼 현재 상황에서 제일 적은 시간을 가진 음식을 뺄 수 있는지 while() 이용해서 조건을 검사합니다.
- (누적되어 빼버린 k값) + (빼버릴 음식의 시간 - 이전 음식의 시간) / (현재 음식의 개수) < 현재 k값

 - 현재 제일 적은 시간을 가진 음식(now)을 뺄 수 있다면 queue.get()으로 빼버리고,
- k값은 업데이트가 now - previous(이전에 빼버린 음식) * (현재 음식의 개수) 빼버리겠죠?

 - 음식이 하나 빠져버리니 현재 음식의 개수(length)도 하나로 줄 것이고, previous 도 업데이트 됩니다.

[4] k값 기준으로 k 값이 작아서 더 이상 현재 제일 적은 시간 음식을 빼버릴 수 없다면 while문은 멈춥니다.

[5] 자 그러면 남은 음식들은 queue값에 있을 테고, 지금 현재 값 계산이 오름 차순으로 정렬으로 했으니 다시 원래 형태로 인덱스 기준 정렬 먼저 합니다. sorted(q.queue, key=lambda x:x[1])

[6] 최종적으로 남은 음식과 최종 k를 이용해서 몇 번째 음식이니 확인하려면  %(mod)를 이용하면 쉽습니다.

최종적으로 남은 음식이 2개이고, k=5번이라고 가정하고 위치를 계산하라면 5%2 = 1 

List에서 인덱스 계산은 0부터 시작이니 k+1은 고려 안해도 됩니다.

from queue import PriorityQueue def solution(food_times, k):     # 만약 더 섭취해야할 음식이 없다면 -1     # k라는 시간 보다 food_times 전체 합보다 크거나 같으면 -1     if sum(food_times) <= k:         return -1         answer = 0         # Priority Queue는 값을 뺄 때 오름차순 정렬되어 가장 적은 값을 버린다.     q = PriorityQueue()     for i in range(len(food_times)):         q.put((food_times[i], i+1)) # Priority Queue를 활용, (food_times, index)를 넣는다.         sum_value = 0 # 누적되는 k에서 빼지는 값     previous = 0 # 이전에 다 먹은 음식 값     length = len(food_times) # 전체 음식 개수     # print(q.queue)         # 현재 상황에서 음식을 다 먹어서 뺄 수 있는지 k랑 비교해야 한다.     # sum_value와 빼버릴 음식의 시간-이전 음식 값 * 현재 음식 개수와 비교     while sum_value + ((q.queue[0][0] - previous) * length)<= k:         now = q.get()[0] # 제일 적은 시간으로 걸린 것부터 Queue에서 빼자.         # 뺀다는 것은 전체 한 바퀴를 돌아야한다.         sum_value += (now - previous) * length         length -= 1 # 다 먹은 음식을 빼게 되므로 전체 길이는 -1만큼 줄어든다.         previous = now # 이전 과일을 업데이트 한다.         # q.queue를 인덱스 기준으로 다시 정렬한다.     result = sorted(q.queue, key=lambda x:x[1])     # 최종적으로 남은 음식 중에서 현재 k가 몇 번째 음식인지 확인해야 합니다. (k - sum_value)% length     return result[(k - sum_value) % len(q.queue)][1]