[백준 2786번] 상근이의 레스토랑 - Java

문제 링크

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

문제

티어: 골드 2
알고리즘: 그리디, 정렬, 우선순위 큐

입력

첫째 줄에 상근이네 레스토랑의 음식의 개수 N(2 ≤ N ≤ 500,000)이 주어진다. 다음 N개의 줄에는 각 음식의 가격 Ai와 Bi가 주어진다. (0 ≤ Ai, Bi ≤ 1,000,000,000)

출력

출력은 총 N개로 이루어져 있다. i번째 줄에는 음식을 i개 시킬 때 필요한 최소 가격을 출력한다.

풀이

i개 시킬 때 필요한 최소 가격을 출력해야 한다.

먼저, 간단하게 생각해 보자
우리는 음식 하나만 Ai 가격이고, 나머지는 Bi다.

그러면 N이 3일 때 Bi를 기준으로만 최소 가격을 만든다면 당연히 Bi 오름차순 순으로 3개 고르면 된다.

여기서 우리는 하나를 Ai로 바꿔줘야 하는데, 모든 음식의 Ai 가격을 고려해야 하기 때문에

1. 이미 선택한 것 중 하나를 Bi -> Ai (내부에서)
2. 선택하지 않은 것 중 Ai가 최소인 음식과 선택한 것 중 Bi가 최대인 음식을 교체 (외부에서)

이 두 경우의 가격을 비교해서 최소인 값을 출력하면 된다.
2번 같은 경우는 말 그대로 적용해주면 되고,

1번은 어떤 Bi를 Ai로 교체해야 할까? A - B의 차이가 가장 작은 음식을 선택해야 한다.

이 아이디어를 기반으로 구현하면 된다.

그리디 + 우선순위 큐 + 정렬 풀이의 시간 복잡도는 O(N * logN)이다.

소스 코드

import java.io.*;
import java.util.*;

class Food implements Comparable<Food> {
    long a, b;
    int ind;
    Food(int ind, long a, long b) {
        this.ind = ind;
        this.a = a;
        this.b = b;
    }
    
    @Override
    public int compareTo(Food o) {
        if(this.a < o.a) {
            return -1;
        } else if(this.a > o.a) {
            return 1;
        }
        return 0;
    }
}

public class Main {
    static int N;
  public static void main(String args[]) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      
      N = Integer.parseInt(br.readLine());
      Food foodsB[] = new Food[N];
      Food foodsA[] = new Food[N];
      long beforeBSum = 0;
      PriorityQueue<Long> a_b = new PriorityQueue<>();
      boolean visited[] = new boolean[N];
      StringBuilder sb = new StringBuilder();
      
      for(int i=0; i<N; i++) {
          StringTokenizer st = new StringTokenizer(br.readLine());
          Food food = new Food(i, Long.parseLong(st.nextToken()), Long.parseLong(st.nextToken()));
          foodsB[i] = food;
          foodsA[i] = food;
      }
      Arrays.sort(foodsA);
      Arrays.sort(foodsB, new Comparator<Food>() {
          @Override
          public int compare(Food o1, Food o2) {
              if(o1.b < o2.b) {
                  return -1;
              } else if(o1.b > o2.b) {
                  return 1;
              }
              return 0;
          }
      });
      
      int cursorA = 0;
      for(int i=0; i<N; i++) {
          beforeBSum += foodsB[i].b;
          visited[foodsB[i].ind] = true;
          a_b.add(foodsB[i].a - foodsB[i].b);
          
          long v1 = beforeBSum + a_b.peek();
          
          if(i == N - 1) {
              sb.append(v1);
              break;
          }
          
          while(visited[foodsA[cursorA].ind]) {
              cursorA += 1;
          }
          
          long v2 = beforeBSum - foodsB[i].b + foodsA[cursorA].a;
          
          sb.append(Math.min(v1, v2)).append("\n");
      }
      
      System.out.println(sb.toString());
  }
}