on1ystar 머릿속을 정리, 기록하는 곳

<2019 KAKAO BLIND RECRUITMENT-python> 무지의 먹방 라이브

30 Jan 2021

코딩테스트 연습 - 무지의 먹방 라이브


문제 요약

회전판에 먹어야 할 N 개의 음식이 있다.

각 음식에는 1부터 N 까지 번호가 붙어있으며, 각 음식을 섭취하는데 일정 시간이 소요된다.

  • 무지는 1번 음식부터 먹기 시작하며, 회전판은 번호가 증가하는 순서대로 음식을 무지 앞으로 가져다 놓는다.
  • 마지막 번호의 음식을 섭취한 후에는 회전판에 의해 다시 1번 음식이 무지 앞으로 온다.
  • 무지는 음식 하나를 1초 동안 섭취한 후 남은 음식은 그대로 두고, 다음 음식을 섭취한다.
    • 다음 음식이란, 아직 남은 음식 중 다음으로 섭취해야 할 가장 가까운 번호의 음식을 말한다.
  • 회전판이 다음 음식을 무지 앞으로 가져오는데 걸리는 시간은 없다고 가정한다.

무지가 먹방을 시작한 지 K 초 후에 네트워크 장애로 인해 방송이 잠시 중단되었다.

무지는 네트워크 정상화 후 다시 방송을 이어갈 때, 몇 번 음식부터 섭취해야 하는지를 알고자 한다.


제한사항

  • food_times 는 각 음식을 모두 먹는데 필요한 시간이 음식의 번호 순서대로 들어있는 배열이다.
  • k 는 방송이 중단된 시간을 나타낸다.
  • 만약 더 섭취해야 할 음식이 없다면 -1을 반환하면 된다.


내가 적어 보는 문제 풀이

가장 기본적인 방법은 food_times를 순회하면서 1회 반복을 1초라 가정하여 각 원소의 값을 -1씩 더해주는 것이다. 이 작업을 총 k번 동안 한 뒤, k+1번에 순회할 food_times의 인덱스+1이 섭취할 음식 번호다. 이럴 경우 정확도는 보장할 수 있지만, 이 문제는 효율성이라는 부분 점수가 있다.

때문에 아래와 같은 효율성 테스트를 위한 제한사항이 추가된다.

효율성 테스트 제한 사항

  • food_times 의 길이는 1 이상 200,000 이하이다.
  • food_times 의 원소는 1 이상 100,000,000 이하의 자연수이다.
  • k는 1 이상 2 x 10^13 이하의 자연수이다.

즉, 최악의 경우 2 x 10^13인 최소 20조 번의 순회 연산을 해야 한다.

이게 어느 정도인지 알아보기 위해 간단하게 테스트를 해봤다.

(혹시 몰라서 적어보면 windows 10, python 3.8.0, PyhCarm에서 테스트)

'''
10^n번의 반복을 하면서
간단한 +연산을 1회 하는데 걸리는 시간을
총 100번 수행해 평균을 냄
'''
n = 6
x = 10**n
accum = 0
for _ in range(100):
		i = 0
    start = time.time()
    for _ in range(x):
        i += 1
    accum += time.time() - start
print(accum / 100)

10^6(100만) → 0.12657963752746582(s)

10^7(1000만) → 1.3903260898590089(s)

10^8(1억) → 14.90573000907898(s)

더 이상은 의미가 없을 것 같다.(측정 하기도 힘듦…)

그래서 고안해 낸 방법은 다음과 같다.

  • 음식을 1초 씩 돌아가면서 먹는 것이 아니라 한 번에 n초 씩 먹는다.
  • 음식들을 1번 순회할 때 음식들의 값(섭취하는 데 남은 시간)에서 n씩 빼준다.
  • 만약 값이 0이 되면 그 음식은 다음 순회에서 제외한다.
  • 이때 n을 정하는 기준은
    1. 남은 음식들이 k(초)보다 적으면 남은 음식들을 k로 나눈다.
    2. 나눈 몫과 남은 음식들 중 가장 값이 작은 음식과 비교해 더 작은 값이 n이 된다.
    3. 남은 음식들이 k보다 많으면 k+1번 째 음식이 답이 된다.

이 방법을 사용하기 위해서는 2가지 사전 작업이 필요하다.

  1. 섭취하는데 걸리는 시간이 가장 적은 순서대로 정렬할 필요가 있다.
  2. 정렬 및 섭취 시간이 0인 음식을 제외하면 음식의 순서들이 뒤바뀌므로 처음에 음식의 순서를 key로 저장해 놓을 딕셔너리가 필요하다.
food_times_dic = {}
    for i, v in enumerate(food_times):
        food_times_dic[i+1] = v
    sorted_dic_q = deque(sorted(map(list, food_times_dic.items()), key=operator.itemgetter(1)))

먼저 food_times의 순서를 key로, 값을 value로 저장할 딕셔너리를 만들어 주고, 이를 정렬한 큐도 만들어 준다. 굳이 deque모듈을 사용한 이유는, 오름차순으로 정렬한 큐에서 추후에 0이된 음식들을 인덱스 0번부터 pop()을 할 때 상수시간 O(1) 효율을 얻기 위함이다.(리스트로 내림차순 정렬한 뒤 반대로 순회해도 되지만 그냥 편의를 위해)

그럼 대충 아래와 같다.

# food_times = [3, 1, 2]
>>> food_times_dic
{1: 3, 2: 1, 3: 2}
>>> sorted_dic_q
deque([[2, 1], [3, 2], [1, 3]])

(참고)

딕셔너리 정렬하기 - sorted(), operator 모듈

이제 k // len(sorted_dic_q)값이 0이 될 때까지 반복하면 된다.

while True:
        n =  k // len(food_times_dic)
        if n >= 1:
            iter_cnt = min(sorted_dic_q[0][1], n)
            k -= len(sorted_dic_q) * iter_cnt
            for food in sorted_dic_q:
                food[1] -= iter_cnt
            while True:
                if food_times_dic == {}:
                    return -1
                if sorted_dic_q[0][1] == 0:
                    i, _ = sorted_dic_q.popleft()  # 섭취 시간이 0인 음식 제외
                    del food_times_dic[i]
                else:
                    break
        else:
            answer = list(food_times_dic.items())[k][0]
            break

iter_cnt = min(sorted_dic_q[0][1], n) 로 섭취 시간이 가장 적은 음식과 n중 더 작은 값으로 iter_cnt를 초기화 한 뒤, 이를 각 음식의 섭취 시간에서 빼준다.

이 과정에서 1바퀴 순회할 시 len(sorted_dic_q) * iter_cnt만큼의 초가 지나기 때문에 k에서 빼준다.

그럼 결과는

정확성은 다 맞지만 효율성 테스트 7.1…

생각해보면 이 방법은 food_times에 섭취 시간이 1씩 증가하는 경우 최악이다.

에를 들어 효율성 테스트 제한 사항에 따라 [1, 2, 3, 4, 5, … , 200000]만 되도 iter_cnt는 계속해서 1로 밖에 초기화되지 않기 때문에(최초에 1이고, 모든 원소에서 1씩 빼기 때문에 다시 최소값이 1이 됨) 총 200000 +199999 + 199998 + … + 1 = 20000100000 = 약 200억 번의 반복을 해야 한다.

위의 방법에서 현재 가장 필요 없는 부분은 가장 적은 섭취 시간을 찾기 위해 정렬하는 부분이다. 이는 혹시나 n(k // len(food_times_dic))보다 섭취 시간이 더 적은 경우 음수가 발생하기 때문에 해놓은 장치같은 건데, 이를 없애고 차라리 발생한 음수 시간만큼 다시 중단된 시간이면서 음식을 넘겨야 하는 k에 더해주는 방식을 떠올렸다.

예를 들어

  • food_times = [1, 4, 3]
  • k = 6

인 경우 k // len(food_times_dic) 은 2이기 때문에 한 번이 2씩 빼주면서(2초씩 섭취하면서) 순회한다.

  • food_times = [-1, 2, 1]
  • k = 0

그러면 2번째 음식의 남은 섭취 시간이 -1이 되기 때문에 이 음식에 1초를 낭비한 셈이 된다.

따라서 이 1초를 다시 k에 더해주는 것이다. 그리고 음수 값이나 0을 가진 음식들은 제외시켜 다시 순회한다.

  • food_times = [2, 1]
  • k = 1

이제 k // len(food_times_dic)는 0보다 작기 때문에 자연스레 food_times의 인덱스 k에 위치한 음식이 답이다.(리스트 인덱스는 0부터 시작하기 때문에)

단, 위에서도 말했듯이 이러면 2를 가진 음식이 이전에 몇 번째 음식이었는 지 모르기 때문에 이를 기억하기 위한 딕셔너리를 만들어 준다.

def solution(food_times, k):
    if sum(food_times) <= k:
        return -1
    answer = 0
    food_times_dic = {}
    for i, v in enumerate(food_times):
        food_times_dic[i+1] = v
    while True:
        iter_cnt = k // len(food_times_dic)
        if iter_cnt >= 1:
            for key, time in list(food_times_dic.items()):
                temp = time - iter_cnt
                if temp <= 0:
                    k -= iter_cnt + temp
                    del food_times_dic[key]
                else:
                    k -= iter_cnt
                    food_times_dic[key] = temp
        else:
            answer = list(food_times_dic.items())[k][0]
            break
    return answer

전체 코드 - on1ystar/algorithm-problem-solving-codes

+추가

첫 번째 방법에서 iter_cnt를 계속 초기화 하지 말고 누적시켜 빼는 방법을 사용하면 가능할 것 같음. 가장 섭취 시간이 적은 음식을 pop()시키고, 그 시간만큼 iter_cnt에 누적한 뒤 다른 원소는 순회하지 않고 다음에 누적된 iter_cnt를 빼면 순회한 효과를 줄 수 있기 때문에 내부의 while문 하나를 없앨 수 있다.

따라서 처음에 k // len(food_times_dic)도 필요없이 오로지 정렬한 값을 가지고 푸는 방법.

이렇게 하면 우선순위 큐를 사용하는 것과 비슷

Related posts