[kakao] 2019 KAKAO BLIND RECRUITMENT - 무지의 먹방 라이브 python

프로그래머스 코딩테스트 연습 - 무지의 먹방 라이브

문제 요약

---

회전판에 먹어야 할 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)

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

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

회전판의 음식들을 무한 순회하면서 먹은 시간만큼 food_times에서 뺄껀데 이때,

1. 각 음식을 1초 동안 돌아가면서 먹는 것이 아닌 n초 동안 먹는다.
   • 이 n을 구하는 방법은 k를 남은 음식의 개수로 나눈 몫이다.
2. k를 남은 음식의 개수로 나눈 나머지 값으로 초기화 한다.
3. 회전판의 모든 음식들을 순회하면서 섭취하는 데 남은 시간에서 n씩 빼준다.
   • 남은 시간이 0 또는 음수면 그냥 넘긴다.
   • 남은 시간보다 n이 더 큰 경우 n에서 남은 시간을 뺀 만큼을 k에 더해준다.
4. 위 1~3을 남은 음식이 없거나 k가 남은 음식의 개수보다 작을 때까지 반복
5. 남은 음식이 없으면 -1 반환
6. k가 남은 음식의 개수보다 작을 때는 남은 섭취 시간이 0보다 큰 음식들 중 k번째 음식의 food_times 인덱스 값 +1 반환

# 이전 코드 생략...
answer = 0
rest_foods_cnt = len(food_times)  # 남은 음식의 개수
while True:
	if rest_foods_cnt == 0:  # 남은 음식이 없으면
    	answer = -1
        break
    rotation_times = k // rest_foods_cnt  # 한 번에 섭취할 시간
    k %= rest_foods_cnt  # 경과 시간(남은 시간)
    if rotation_times == 0:
        break
    for i in range(len(food_times)):
        if food_times[i] <= 0:  # 이미 전부 섭취한 음식
            continue
        if food_times[i] > rotation_times:
            food_times[i] -= rotation_times
        else:  # 남은 섭취 시간보다 한 번에 섭취할 시간이 더 큰 경우
            k += rotation_times - food_times[i]
            food_times[i] = 0
            rest_foods_cnt -= 1
# 이후 코드 생략...

예를 들어

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

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

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

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

따라서 이 1초를 다시 k에 더해주는 것이다.

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

위 경우 k보다 남은 음식의 개수가 더 크기 때문에 남은 음식 중 1번째 음식의 인덱스 값 +1인 2를 반환한다.

 

전체 코드 - on1ystar님의 Github