백준 1826번 연료 채우기 (JAVA)

https://www.acmicpc.net/problem/1826

1826번: 연료 채우기

 

저는 우선순위 큐를 통해 문제를 해결하였습니다. 

우선순위 큐에는 연료를 넣었고 큰 수가 앞에 나오도록 하였습니다.

주유소를 위치에 따라 정렬하고 현재 연료보다 작으면 모두 우선선위 큐에 연료를 넣었습니다.

목표지점까지 연료가 되지 않는다면, 우선순위 큐에서 하나씩 빼서 현재 연료에 추가하였습니다.

위의 과정을 반복하여 연료가 목표지점까지 갈 수 있다면 개수만큼 리턴하고 갈 수 없다면 -1을 리턴하도록 하였습니다.

 

package BOJ.greedy;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
import java.util.function.Function;

public class BOJ_1826 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        Function<String,Integer> stoi = Integer::parseInt;
        int n = stoi.apply(st.nextToken());
        List<int[]> list = new LinkedList<>();
        for(int i = 0 ; i < n ; i++){
            st = new StringTokenizer(br.readLine());
            int distance = stoi.apply(st.nextToken());
            int fuel = stoi.apply(st.nextToken());
            list.add(new int[] {distance,fuel});
        }
        st = new StringTokenizer(br.readLine());
        int distance = stoi.apply(st.nextToken());
        int fuel = stoi.apply(st.nextToken());
        int result = cal(list,distance,fuel,n);
        System.out.println(result);
    }
    private static final int NOT_FOUND = -1;
    private static int cal(List<int[]> list, int distance, int fuel, int n) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        Collections.sort(list,(o1,o2)->o1[0]-o2[0]);
        int index = 0;
        int cnt = 0;
        while(true){

            while(index < n && list.get(index)[0] <= fuel){
                pq.offer(list.get(index)[1]);
                index++;
            }
            if(!pq.isEmpty() && fuel < distance){
                fuel += pq.poll();
                cnt++;
            }else{
                break;
            }
        }
        if(fuel >= distance){
            return cnt;
        }
        return NOT_FOUND;
    }
}