https://bong-f.tistory.com/267

동빈북

ch11 그리디문제

볼링공 고르기

• 코드

무지의 먹방 라이브

• 문제
• 동빈북파이썬
• 동빈북자바
• 코드
• 이 해설 유튜브 를 보고 동빈북 코드를 이해하려고 하면 이해가 간다.
• sort는 https://velog.io/@bongf/210729-Algorithms-TIL 참고
• 큐는 https://velog.io/@bongf/210814-Algorithms-TIL#%EC%9E%90%EB%B0%94%EC%97%90%EC%84%9C-%ED%9E%99 https://velog.io/@bongf/210909-Algorithms-TIL 참고

subList에 대해서 알게되었다.

• 리스트 부분 정렬
• sublist

 public static void main(String[] args) {
        
        List<Integer> t = new ArrayList<>();
        t.add(0, 5);
        t.add(1, 7);
        t.add(2, 1);
        t.subList(1, t.size()).sort(Integer::compareTo);
        System.out.println(t); // [5, 1, 7]

• 동빈북 풀이랑 유툽 적절히 섞어서

package etc;

import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.stream.Collectors;

public class Practice {
    public static void main(String[] args) {
        Practice p = new Practice();
        System.out.println(p.solution(new int[]{3,1,2}, 5L));
    }

    public int solution(int[] food_times, long k) {
        long sum = 0;

        PriorityQueue<Food> foods = new PriorityQueue<>();
        for (int i = 0; i < food_times.length; i++) {
            foods.add(new Food(i+1, food_times[i]));
            sum += food_times[i];
        }
        if (sum <= k) {
            return -1;
        }

        long ate = 0;
        long previous = 0;
        long length = food_times.length;
        while ((ate + (foods.peek().time - previous) * length) <= k) {
            Food now = foods.poll();
            ate += (now.time - previous) * length;
            length--;
            previous = now.time;
        }

        List<Food> collect = foods.stream().sorted(CompIdx).collect(Collectors.toList());
        System.out.println(collect);
        return collect.get((int) ((k - ate) % length)).idx;
    }

    Comparator<Food> CompIdx = new Comparator<Food>() {
        @Override
        public int compare(Food f1, Food f2) {
            return f1.idx - f2.idx;
        }
    };
}


class Food implements Comparable<Food> {
    int idx;
    int time;

    public Food(int idx, int time) {
        this.idx = idx;
        this.time = time;
    }

    @Override
    public int compareTo(Food food) {
        return this.time - food.time;
    }
}