[백준] 1826 연료 채우기 - JAVA

문제

연료 채우기
처음에 해당 문제를 풀때는 그래프를 이용해 풀어봤지만 역시 시간 복잡도 계산을 안하고 하니 바로 시간 초과가 나오게 됐다.

내가 그래프로 푼건 주유소를 들릴지 말지를 다 돌려보는 로직이라 조그만 계산해봐도 2^N의 시간복잡도를 가진다.
여기서 이미 구한 최솟값보다 작은 값의 주유소를 들린다면 return을 해주는등 개선해 보았지만 역시나 시간초과.. 2^N의 시간복잡도는 도저히 이길 수 없을듯 싶었다.

그럼 남은건 그리디뿐.. 하지만 그리디로 풀려고 생각해봐도 떠오르지가 않았다.

그래프로 풀려고 안간힘을 쓴 탓에 머리가 아파와 정답을 봐버렸다,,

정답을 봤는데 저번에 풀어본 그리디 문제랑 비슷한 느낌의 로직이었다.
이전에는 풀어서 맞췄는데 못풀었다니.. ㅠㅠ 역시 어떤 알고리즘을 쓰는지 알고푸는거랑 모르고 푸는건 난이도 차이가 상당한것 같다.

풀이

먼저 입력으로 받은 주유소들을 거리순으로 정렬해준다. 이때 우선순위큐를 사용하여 정렬해주었다.

입력을 다 받았으면 현재 가지고 있는 양의 연료로 갈 수 있는 거리를 가진 주유소가 있다면 다른 우선순위 큐에 해당 주유소에서 얻을 수 있는 연료의 양을 내림차순으로 넣어준다.

즉 현재 갈 수 있는 주유소중에서 연료의 양을 제일 많이 주는 주유소를 방문하는 그리디 문제라는 것!

만약 갈 수 있는 주유소가 없다면 정답 변수에 -1을 넣어준다.
갈 수 있는 주유소가 있다면 현재 가지고 있는 연료에 주유소에서 주는 연료의 양만큼 더해준다.

이 로직을 현재 가지고 있는 연료의 양이 가야하는 거리보다 크거나 같아질때까지 반복해준다.

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
  static int N,L,P;
  static GasStation[] gasStations;
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    N = Integer.parseInt(st.nextToken()); //주유소의 개수
    PriorityQueue<GasStation> info = new PriorityQueue<>();
    gasStations = new GasStation[N];
    for(int i=0; i<N; i++) {
      st = new StringTokenizer(br.readLine());
      info.offer(new GasStation(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
    }
    st = new StringTokenizer(br.readLine());
    L = Integer.parseInt(st.nextToken());
    P = Integer.parseInt(st.nextToken());
    int answer = 0;

    PriorityQueue<Integer> q = new PriorityQueue<>(Collections.reverseOrder());

    //  현재 기름의 양으로 갈 수 있는 주유소만 q에 넣는데 갈 수 있는 주유소중에서 가장 큰 양을 주는 주유소 먼저 큐에 저장한다.
    // 만약 q가 비었다면 갈 수 있는 주유소가 없다는 뜻이므로 -1을 리턴한다.
    while(P < L) {
      while(!info.isEmpty() && P >= info.peek().dist) {
        GasStation curr = info.poll();
        q.offer(curr.weight);
      }
      if(q.isEmpty()) {
        answer = -1;
        break;
      }
      P = P + q.poll();
      answer++;
    }
    System.out.println(answer);
  }
  public static class GasStation implements Comparable<GasStation>{
    int dist,weight;
    GasStation(int dist, int weight) {
      this.dist = dist;
      this.weight = weight;
    }
    @Override
    public int compareTo(GasStation o) {
      return this.dist - o.dist;
    }

  }
}

교훈

시간복잡도 계산을 철저히 하자 안그러면 머리만 아파진다.