백준 1715 - 카드 정렬하기 (자바 - 그리디)

 

생각보다 간단히 풀 수 있었던 골드 티어 문제(골드 4)

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

1715번: 카드 정렬하기

여러 갯수를 가지고 있는 카드 뭉치들이 주어지고, 각 카드들을 정렬된 순서로 모두 합치는 데 필요한 최소 비교 횟수를 구하는 문제이다.

이 문제의 경우 최소 비교횟수를 구하려면 확정적으로 가장 작은 카드 갯수를 가지고 있는 카드 뭉치들을 합쳐나가면 된다.

정렬된 리스트를 기준으로 매 연산때마다 최적의 선택을 해야 하므로 그리디 알고리즘에 해당된다.

 

- Main.java

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		PriorityQueue<Integer> cardQueue = new PriorityQueue<Integer>();
		List<Integer> list = new ArrayList<Integer>();
		
		int count = Integer.parseInt(br.readLine());
		
		for(int i = 0; i < count; i++) {
			cardQueue.offer(Integer.parseInt(br.readLine()));
		}
		
		int sum = Integer.MAX_VALUE;
		if(count == 1) {
			sum = 0;
		}
		else {
			while(true) {
				int number1 = cardQueue.poll();
				int number2 = 0;
				if(!cardQueue.isEmpty())
					number2 = cardQueue.poll();
				
				list.add(number1+number2);
				if(cardQueue.isEmpty())
					break;
				cardQueue.offer(number1 + number2);
			}
			
			sum = list.stream().mapToInt(Integer::intValue).sum();
		}

		bw.write(sum + "\n");
		bw.flush();
		bw.close();
	}
}

 

1. 입력으로 들어온 카드 들을 오름차순 정렬하기 위해 우선순위 큐에 적재한다.(값들이 적재될 때마다 자동으로 정렬된다.)

2. 큐에서 가장 앞에 있는 카드 뭉치 둘을 뽑아(큐에서 크기가 가장 작은 카드 뭉치 2개) 비교 횟수를 구한다음(둘의 갯수를 합산하면 된다.) 해당 결과를 우선순위 큐와 결과 리스트에 삽입해준다.

3. 우선순위 큐가 빌 때까지 2의 과정을 반복한다.

4. 우선순위 큐가 비어지고 나면 결과 리스트에 적재되어 있는 값들을 모두 합해주는 것으로 최소 비교 횟수 를 구할 수 있다.