[백준 - 6173번] Pearl Pairing - Java

문제 링크

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

문제

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

입력

• 첫 번째 줄에는 두 개의 정수 N과 C가 주어집니다.
• 다음 C개의 줄에는 각 줄마다 i번째 색의 진주의 개수 C_i가 주어집니다.

출력

N/2개의 줄에 걸쳐, i번째 줄에는 두 정수 a_i와 b_i를 출력합니다. 이는 Bessie가 색 a_i의 진주와 색 b_i의 진주를 짝지을 수 있음을 나타냅니다.

풀이

N/2개의 줄에 걸쳐, i번째 줄에 두 정수 a_i와 b_i를 출력해야 한다.

문제에 보면, 주어진 테스트 케이스에 대해 짝짓기는 항상 가능하다고 한다.

그래서 짝을 짓기 위한 최선의 선택을 하는 경우는 무조건 가능한 경우임을 알 수 있다.

최선의 선택은 무엇일까?

가장 많은 진주를 가지고 있는 색을 생각해 보자,

이 진주들은 같은 색이기 때문에 짝을 지어 줄 수 없는데, 가장 많은 개수를 가지고 있다.

그래서 이 진주에 개수를 우선적으로 줄여주는 것이 최선의 선택이 된다.

짝이 되는 다른 색의 진주 또한 그 다음 많은 개수를 가진 진주를 선택하는 것이 최선이 된다.

왜냐하면 앞에서 말했다 싶이 가장 많은 개수를 가진 진주를 우선적으로 짝을 지어주는 것이 최선의 선택이 되기 때문이다.

핵심은 상대적으로 많은 같은 색의 진주를 없애는 것이다.

그래서 진주의 개수 기준으로 내림차순으로 정렬하는 우선순위 큐를 이용해서 두 개씩 poll()하고, 다시 add()하고를 반복하면 된다.

이 풀이의 시간 복잡도는 매번 진주 2개씩 짝지어주기 때문에 O(N/2)이다.

소스 코드

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

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

public class Main {
  public static void main(String args[]) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      int N = Integer.parseInt(st.nextToken());
      int C = Integer.parseInt(st.nextToken());
      
      PriorityQueue<Jinju> pQue = new PriorityQueue<>();
      
      for(int i=1; i<=C; i++) {
          pQue.add(new Jinju(Integer.parseInt(br.readLine()), i));
      }
      
      StringBuilder sb = new StringBuilder();
      while(!pQue.isEmpty()) {
          //비어있지 않다면 무조건 두 종류 이상의 진주가 남아있음
          Jinju fst = pQue.poll();
          Jinju sec = pQue.poll();
          
          sb.append(fst.ind).append(" ").append(sec.ind).append("\n");
          
          fst.c -= 1;
          sec.c -= 1;
          
          if(fst.c > 0) {
              pQue.add(fst);
          }
          
          if(sec.c > 0) {
              pQue.add(sec);
          }
      }
      
      System.out.println(sb.toString().trim());
  }
}