무지의 먹방 라이브
1. Time, index 저장
int len = food_times.length;
List<Food> foods = new LinkedList<Food>();
// time과 index 넣어줌
for (int i = 0; i < len; i++) {
foods.add(new Food(food_times[i], i + 1));
}
Food 객체
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 index;
}
@Override
public int compareTo(Food other) {
return Integer.compare(this.time, other.time);
}
}- Time 정렬
// time정렬
Collections.sort(foods);
- 가장 적은 time 접시를 배열의 길이만큼 곱함
int pre = 0;
int i = 0;
for (Food f : foods) {
// 한 접시의 시간
long time = f.getTime() - pre;
// 그 시간이 0이 아니면
if (time != 0) {
// 가장 작은 시간 * 총 접시의 개수
long spend = time * len;
// 빼줘야하는 값과 비교
- 위의 값을 k와 비교해 크거나 같으면 그냥 빼주고 작으면 k를 접시의 개수로 나눈 나머지를 구해 index 를 구한다.
if (spend <= k) {
// 크면 그냥 빼줌
k -= spend;
pre = f.getTime();
} else {
// 작으면 나눈 나머지 구해서
k = k % len;
// index 정렬
foods.subList(i, food_times.length).sort(new Comparator<Food>() {
@Override
public int compare(Food a, Food b) {
return Integer.compare(a.getIndex(), b.getIndex());
}
});
// 나머지값의 index 리턴
return foods.get(i + (int) k).getIndex();
}
}
len--;
i++;
}
return -1;
}
}
Ex)
전체 코드
자바 -> 안됨
package jifrozen.그리디;
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 index;
}
@Override
public int compareTo(Food other) {
return Integer.compare(this.time, other.time);
}
}
class Solution {
public int solution(int[] food_times, long k) {
int len = food_times.length;
ArrayList<Food> foods = new ArrayList<>();
// time과 index 넣어줌
for (int i = 0; i < len; i++) {
foods.add(new Food(food_times[i], i + 1));
}
// time정렬
Collections.sort(foods);
// 전 접시 시간 계산
int pre = 0;
for (int i = 0; i < len; i++) {
// 한 접시의 시간
int time = foods.get(i).getTime() - pre;
// 그 시간이 0이 아니면
if (time != 0) {
// 가장 작은 시간 * 총 접시의 개수
int spend = time * len;
// 빼줘야하는 값과 비교
if (spend <= k) {
// 크면 그냥 빼줌
k -= spend;
pre = foods.get(i).getTime();
} else {
// 작으면 나눈 나머지 구해서
k = k % len;
// index 정렬
Collections.sort(foods, new Comparator<Food>() {
@Override
public int compare(Food a, Food b) {
return Integer.compare(a.getIndex(), b.getIndex());
}
});
// 나머지값의 index 리턴
return foods.get((int) (k)).getIndex();
}
}
// 다 먹은 접시 치우기
len -= 1;
foods.remove(foods.get(i));
}
return -1;
}
} 최종 자바 -> 성공
package jifrozen.그리디;
import java.util.*;
/*
성공 코드
*/
public class Solution {
public int solution(int[] food_times, long k) {
int len = food_times.length;
List<Food> foods = new LinkedList<Food>();
// time과 index 넣어줌
for (int i = 0; i < len; i++) {
foods.add(new Food(food_times[i], i + 1));
}
// time정렬
Collections.sort(foods);
int pre = 0;
int i = 0;
for (Food f : foods) {
// 한 접시의 시간
long time = f.getTime() - pre;
// 그 시간이 0이 아니면
if (time != 0) {
// 가장 작은 시간 * 총 접시의 개수
long spend = time * len;
// 빼줘야하는 값과 비교
if (spend <= k) {
// 크면 그냥 빼줌
k -= spend;
pre = f.getTime();
} else {
// 작으면 나눈 나머지 구해서
k = k % len;
// index 정렬
foods.subList(i, food_times.length).sort(new Comparator<Food>() {
@Override
public int compare(Food a, Food b) {
return Integer.compare(a.getIndex(), b.getIndex());
}
});
// 나머지값의 index 리턴
return foods.get(i + (int) k).getIndex();
}
}
len--;
i++;
}
return -1;
}
}
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 index;
}
@Override
public int compareTo(Food other) {
return Integer.compare(this.time, other.time);
}
}안되는 이유?
계속 ArrayList 에서 get remove해서 그런가...?
파이썬 -> 테스트 통과
from operator import itemgetter
def solution(food_times, k):
foods = []
for i in range(len(food_times)):
foods.append([food_times[i], i])
foods.sort()
pretime = 0
n = len(food_times)
for i in range(len(food_times)):
time = foods[i][0] - pretime
if time != 0:
spend = time * n
if spend <= k:
k -= spend
pretime = foods[i][0]
else:
k %= n
sublist = sorted(foods[i:], key=itemgetter(1))
return sublist[k][1]+1
n -= 1
return -1
print(solution([3,5,1,6,5,3], 20)) 