기본 코드 제공
https://programmers.co.kr/learn/courses/30/lessons/42891
제한 사항
| 난이도 | 풀이 시간 | 시간 제한 | 메모리 제한 |
|---|---|---|---|
| 2.5 | 30분 | 1초 | 128MB |
문제
평소 식욕이 왕성한 무지는 자신의 재능을 뽐내고 싶어졌고 고민 끝에 카카오 TV 라이브 방송을 하기로 마음먹었습니다. 그냥 먹방을 하면 다른 방송과 차별성이 없기 때문에 무지는 다음과 같이 독특한 방식을 생각해냈습니다.
회전판에 먹어야 할 N개의 음식이 있습니다. 각 음식에는 1부터 N까지 번호가 붙어있으며, 각 음식을 섭취하는데 일정 시간이 소요됩니다. 무지는 다음과 같은 방법으로 음식을 섭취합니다
1. 무지는 1번 음식부터 먹기 시작하며, 회전판은 번호가 증가하는 순서대로 음식을 무지 앞으로 가져다 놓습니다.
2. 마지막 번호의 음식을 섭취한 후에는 회전판에 의해 다시 1번 음식이 무지 앞으로 옵니다.
3. 무지는 음식 하나를 1초 동안 섭취한 후 남은 음식은 그대로 두고, 다음 음식을 섭취합니다.
다음 음식이란, 아직 남은 음식 중 다음으로 섭취해야 할 가장 가까운 번호의 음식을 말합니다.
4. 회전판이 다음 음식을 무지 앞으로 가져오는 데 걸리는 시간은 없다고 가정합니다.무지가 먹방을 시작한 지 K초 후에 네트워크 장애로 인해 방송이 잠시 중단되었습니다. 무지는 네트워크 정상화 후 다시 방송을 이어갈 때, 몇 번 음식부터 섭취해야 하는지를 알고자 합니다. 각 음식을 모두 먹는 데 필요한 시간이 담겨 있는 배열 food_times, 네트워크 장애가 발생한 시간 K초가 매개변수로 주어질 때 몇 번 음식부터 다시 섭취하면 되는지 return 하도록 solution 함수를 완성하세요.
입력 조건
- food_times는 각 음식을 모두 먹는 데 필요한 시간이 음식의 번호 순서대로 들어 있는 배열입니다.
- k는 방송이 중단된 시간을 나타냅니다.
정확성 테스트 제한 사항
- 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¹³ 이하의 자연수입니다.
출력 조건
- 만약 더 섭취해야 할 음식이 없다면 -1을 반환하면 됩니다.
입출력 예시
food_times k result [3, 1, 2] 5 1
입출력 예시에 대한 설명
0 ~ 1초 동안에 1번 음식을 섭취한다. 남은 시간은 [2, 1, 2]입니다.
1 ~ 2초 동안에 2번 음식을 섭취한다. 남은 시간은 [2, 0, 2]입니다.
2 ~ 3초 동안에 3번 음식을 섭취한다. 남은 시간은 [2, 0, 1]입니다.
3 ~ 4초 동안에 1번 음식을 섭취한다. 남은 시간은 [1, 0, 1]입니다.
4 ~ 5초 동안에 (2번 음식은 다 먹었으므로) 3번 음식을 섭취한다. 남은 시간은 [1, 0, 0]입니다.
5초에서 네트워크 장애가 발생했습니다. 1번 음식을 섭취해야 할 때 중단되었으므로, 장애 복구 후에 1번 음식부터 다시 먹기 시작하면 됩니다.
소스 코드
function solution(food_times, k) {
const len = food_times.length;
let foods = food_times.map((time, index) => {
return { index: index + 1, time };
}).sort((a, b) => a.time - b.time);
let previous = 0;
for (let i = 0; i < len ; i++) {
const currentTime = foods[i].time;
const remainFoodsLen = len - i;
const eatTime = (currentTime - previous) * remainFoodsLen;
previous = currentTime;
if (k < eatTime) {
foods = foods.slice(i).sort((a,b) => a.index - b.index);
return foods[k % remainFoodsLen].index;
}
k -= eatTime;
}
return -1;
}정답
import heapq
def solution(food_times, k):
# 전체 음식을 먹는 시간보다 k가 크거나 같다면 -1
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) # 남은 음식의 개수
# sum_value + (현재 음식 시간 - 이전 음식 시간) * 현재 음식 개수와 k 비교
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]느낀 점
COS Pro 2급 준비를 포함해 지금껏 풀었던 알고리즘 문제 중 해결 시간이 가장 오래 걸린 문제였다. 문제가 길어 읽고 이해하는데 많은 시간이 걸렸을뿐더러, 효율성 검사에서 계속 시간 초과되었다. 정답을 봐도 이해가 가지 않아서 유튜브 강의 영상을 봤다. 푸는 방법을 이해한 뒤 내 방식대로 풀어보았지만 계속 실패하였다. 우선순위 큐와 파이썬 코드는 JS로 문제를 푸는데 많은 도움을 주지 못해서 다른 사람이 JS로 풀이한 방법을 참고하여 코드를 작성했다.
이해한 풀이 방법은 다음과 같다.
1. 음식의 번호와 걸리는 시간을 함께 저장한다. (객체 형태로 저장하였음.)
2. 음식을 먹는 데 걸리는 시간이 적은 순으로 정렬한다.
3. 시간이 가장 적은 순서대로 음식을 다 먹는 데 걸리는 시간을 구한다.
(음식을 먹는 데 걸리는 시간 * 총 음식 개수)
4. 네트워크 장애로 인한 방송 중단 시간을 음식을 먹을 수 있는 남은 시간이라고 할 때,
음식을 다 먹는 데 걸리는 시간보다 남은 시간이 적다면 그 음식은 먹지 못한 것이다.
5. 만약 남은 시간이 더 많다면 그다음 음식을 다 먹는 데 걸리는 시간을 구한다.
(현재 음식 시간 - 방금 전에 다 먹은 음식 시간) * 남은 음식 개수
첫 번째 음식의 시간만큼 현재 음식도 먹었으므로 이렇게 계산한다.
예를 들어 첫 번째 음식의 시간이 2이고, 현재 음식의 시간이 3이라면
첫 번째 음식을 다 먹으면서 현재 음식도 2번을 먹었기 때문에 현재 음식 시간은 1이 남는다.
6. 음식을 먹을 수 있는 남은 시간보다 현재 음식을 다 먹는 시간이 더 크다면
남은 음식 중 먹어야 할 음식은 무엇인지 구한다.
(방송 중단 시간 - 지금까지 먹는 데 쓴 시간) % 남은 음식 개수 ==> 먹어야 할 음식의 인덱스
참고 블로그
