[Algorithm]無知な食いしん坊生放送Java
33238 ワード
無知な食いしん坊生活
1.Time、インデックスの保存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);
}
}
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));
}
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정렬
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;
}
}
完全なコード
JAva->使用不可
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;
}
} 最終java->成功
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を削除しているからなのか…?
Python->テストに合格
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)) Reference
この問題について([Algorithm]無知な食いしん坊生放送Java), 我々は、より多くの情報をここで見つけました https://velog.io/@jifrozen/Algorithm-무지テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol