백준 1715 [카드 정렬하기] - JAVA

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

1715번: 카드 정렬하기

 

풀이

1. 두 묶음의 카드를 골라야한다.

  => Q : 어떤 기준에 의해서 두 묶음의 카드를 골라야할까?

       A : 문제 예시를 보고 가장 작은 카드 묶음 2개를 골라야하겠다.

2. 두 묶음의 카드를 합친다음에도 가장 작은 카드묶음 두개를 골라야한다.

  PriorityQueue(우선순위 큐)를 이용하면 정렬을 알아서 해준다.

 

PriorityQueue(우선순위 큐)에 대한 정보는 여기를 클릭

 

주의사항

N의 범위는 (1 ≤ N ≤ 100,000) 다음과 같다.

N이 1일경우 카드를 섞는 횟수는 0번이다.

항상 문제를 풀때 범위를 확인하자

 

소스코드

package algorithm.greedy;

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

/**
 * 카드 정렬하기 
 */
public class Q1715 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N  = Integer.parseInt(br.readLine());
		int nReturn = 0;
		
		//우선순위큐
		//기본적으로 정수형에 대해서는 오름차순 정렬한다.
		PriorityQueue<Integer> qu = new PriorityQueue<Integer>();
		for(int nIdx = 0 ; nIdx < N ; nIdx++) {
			qu.add(Integer.parseInt(br.readLine()));
		}
		
		while(qu.size() > 2) {
			//1.선택 and 2.적절성검사
			//가장작은 두개의 카드묶음을 선택한다.
			//우선순위큐를 사용하였기에 poll하는것만으로 적절성검사가 완료된다.
			//가장작은 두개의 묶음을 먼저 합친다
			int nTargetA = qu.poll();
			int nTargetB = qu.poll();
			nReturn += nTargetA + nTargetB;
			qu.add(nTargetA + nTargetB);
		}
		
		if(qu.size() == 1) {
			// N의 범위가 (1 ≤ N ≤ 100000)
			// N이 1일경우 비교횟수는 0이다
			System.out.println(0);
			return;
		}else {
			while(!qu.isEmpty()) {
				nReturn += qu.poll();
			}
		}
		System.out.println(nReturn);
		
	}

}