-
평소 식욕이 왕성한 무지는 자신의 재능을 뽐내고 싶어 졌고 고민 끝에 카카오 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 이하의 자연수이다.
-
입출력 예 #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번 음식부터 다시 먹기 시작하면 된다.
1. 그리디 알고리즘
## 테스트 케이스 50%정도 통과
def solution(food_times, k):
plus = 0
for _ in range(k):
rotate = plus % (len(food_times))
#print('plus', plus)
#print('rotate',rotate)
if(food_times[rotate] == 0):
plus += 1
rotate = plus % (len(food_times))
#print('change_rotate', rotate)
food_times[rotate] -= 1
plus += 1
#print(food_times)
if food_times[(rotate+1)%3] == 0:
answer = -1
else:
answer = ((rotate+1) % 3) + 1
return answer
#print(solution([3,1,2], 5))
정답
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]
-
모든 음식을 시간을 기준으로 정렬한 뒤에, 시간이 적게 걸리는 음식부터 제거해 나가는 방식을 이용하면 된다.
- 이를 위해 우선순위 큐를 이용하여 구현할 수 있다.
-
3개의 음식이 있으며,
K = 15라고 해보자-
1번 음식: 8초 소요
-
2번 음식: 6초 소요
-
3번 음식: 4초 소요
1) 초기 단계에서는 모든 음식을 우선순위 큐(최소 힙)에 삽입한다.
-
마지막에
K초 후에 먹어야 할 음식의 번호를 출력해야 하므로 우선순위 큐에 삽입할 때(음식 시간, 음식 번호)의 튜플 형태로 삽입한다.-
전체 남은 시간(K): 15초
-
남은 음식: 3개
-
2) 첫 단계에서는 가장 적게 걸리는 음식인
3번 음식을 뺀다.-
다만, 음식이 3개 남아 있기에
3(남은 음식의 개수) x 4(3번 음식을 먹는 시간) = 12를 빼야한다.- 즉 다 먹는 데 12초가 걸린다는 소리다.
-
전체 남은 시간이 15초에서 3초로 줄게 된다.
-
전체 남은 시간(K): 15초
-
남은 음식: 2개
-
먹은 음식들: (4, 3)
-
3) 이번 단계에서는 2번 음식을 빼야 한다.
-
전체 음식이 2개 남았으므로
2(남은 음식의 개수) x 2(2번 음식을 다 먹는 시간) = 4초가 된다. -
현재 남은 시간이 3초인데, 이는 4보다 작으므로 빼지 않도록 한다.
-
'다음으로 먹어야 할 음식 번호'를 찾아서 출력하면 된다.
- 전체 남은 시간이 3초이므로, 4번째 음식의 번호를 출력하면 정답이다.
-
2. C++ 코드
#include <bits/stdc++.h>
using namespace std;
bool compare(pair<int, int> a, pair<int, int> b) {
return a.second < b.second;
}
int solution(vector<int> food_times, long long k) {
// 전체 음식을 먹는 시간보다 k가 크거나 같다면 -1
long long summary = 0;
for (int i = 0; i < food_times.size(); i++) {
summary += food_times[i];
}
if (summary <= k) return -1;
// 시간이 작은 음식부터 빼야 하므로 우선순위 큐를 이용
priority_queue<pair<int, int> > pq;
for (int i = 0; i < food_times.size(); i++) {
// (음식 시간, 음식 번호) 형태로 우선순위 큐에 삽입
pq.push({-food_times[i], i + 1});
}
summary = 0; // 먹기 위해 사용한 시간
long long previous = 0; // 직전에 다 먹은 음식 시간
long long length = food_times.size(); // 남은 음식의 개수
// summary + (현재의 음식 시간 - 이전 음식 시간) * 현재 음식 개수와 k 비교
while (summary + ((-pq.top().first - previous) * length) <= k) {
int now = -pq.top().first;
pq.pop();
summary += (now - previous) * length;
length -= 1; // 다 먹은 음식 제외
previous = now; // 이전 음식 시간 재설정
}
// 남은 음식 중에서 몇 번째 음식인지 확인하여 출력
vector<pair<int, int> > result;
while (!pq.empty()) {
int food_time = -pq.top().first;
int num = pq.top().second;
pq.pop();
result.push_back({food_time, num});
}
sort(result.begin(), result.end(), compare); // 음식의 번호 기준으로 정렬
return result[(k - summary) % length].second;
}
3. Java 코드
import java.util.*;
class Food implements Comparable<Food> {
private int time;
private int index;
public Food(int time, int index) {
this.time = time;
this.index = index;
}
public int getTime() {
return this.time;
}
public int getIndex() {
return this.index;
}
// 시간이 짧은 것이 높은 우선순위를 가지도록 설정
@Override
public int compareTo(Food other) {
return Integer.compare(this.time, other.time);
}
}
class Solution {
public int solution(int[] food_times, long k) {
// 전체 음식을 먹는 시간보다 k가 크거나 같다면 -1
long summary = 0;
for (int i = 0; i < food_times.length; i++) {
summary += food_times[i];
}
if (summary <= k) return -1;
// 시간이 작은 음식부터 빼야 하므로 우선순위 큐를 이용
PriorityQueue<Food> pq = new PriorityQueue<>();
for (int i = 0; i < food_times.length; i++) {
// (음식 시간, 음식 번호) 형태로 우선순위 큐에 삽입
pq.offer(new Food(food_times[i], i + 1));
}
summary = 0; // 먹기 위해 사용한 시간
long previous = 0; // 직전에 다 먹은 음식 시간
long length = food_times.length; // 남은 음식의 개수
// summary + (현재의 음식 시간 - 이전 음식 시간) * 현재 음식 개수와 k 비교
while (summary + ((pq.peek().getTime() - previous) * length) <= k) {
int now = pq.poll().getTime();
summary += (now - previous) * length;
length -= 1; // 다 먹은 음식 제외
previous = now; // 이전 음식 시간 재설정
}
// 남은 음식 중에서 몇 번째 음식인지 확인하여 출력
ArrayList<Food> result = new ArrayList<>();
while (!pq.isEmpty()) {
result.add(pq.poll());
}
// 음식의 번호 기준으로 정렬
Collections.sort(result, new Comparator<Food>() {
@Override
public int compare(Food a, Food b) {
return Integer.compare(a.getIndex(), b.getIndex());
}
});
return result.get((int) ((k - summary) % length)).getIndex();
}
}
