[백준/Java] 1715번 카드 정렬하기

 

 

문제 풀이

우선순위 큐로 풀어야하는 문제이다.

오름차순으로 정렬된 값들 중 가장 작은 두 값을 더해 나가야 최소값을 구할 수 있기 때문이다.

예제 입력이 1개 밖에 안 나와있는데 이 예제만 생각해서 문제를 풀면 틀릴 수도 있다.

 

BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
PriorityQueue<Integer> queue = new PriorityQueue<>();

int N = Integer.parseInt(st.nextToken());
for(int i=0; i<N; i++) {
    queue.add(Integer.parseInt(bf.readLine()));
}

1. 문제에서 주어진 입력을 위한 코드를 작성한다.

우선순위 큐인 queue를 생성하고, 입력에서 주어진 N개의 수를 queue에 더한다.

 

if(N == 1) {
    System.out.println(0);
    return;
}

2. N이 1이라면 비교할 카드가 없으므로 0을 출력한다.

 

int sum = 0;
while(true) {
    if(queue.size() == 1) break;

    int num1 = queue.poll();
    int num2 = queue.poll();

    sum += num1 + num2;
    queue.add(num1 + num2);
}

3. 비교한 횟수를 담을 sum 변수를 생성한다.

while문을 돌며 특정한 조건을 만나면 while문을 빠져나온다.

 

if(queue.size() == 1) break;

그 조건은 queue의 사이즈가 1일 때이다. 1이면 더이상 비교할 카드가 없으므로(카드 2개에 대해 비교해야하니까)

 

int num1 = queue.poll();
int num2 = queue.poll();

PriorityQueue를 사용하고 있기 때문에 오름차순으로 정렬되어있어서 2개의 값을 빼줘 각각 num1, num2 변수에 대입한다.

 

sum += num1 + num2;
queue.add(num1 + num2);

두 값을 sum에 더하고,

더한 값을 queue에 다시 집어넣는다.

 

 

이에 대한 예시를 들어보겠다.

현재 queue에 오름차순으로 정렬된 수 5개가 있다.

 

queue에서 가장 작은 두 수인 10과 20을 꺼내 더한 뒤 다시 queue에 넣는다.

sum에 10과 20을 더한다. (sum = 30)

나는 처음에 30을 넣지 않고 그냥 30 + 60 , (30+60) + 73 이런식으로 더해서 틀렸다.

우선순위 큐의 특징에 의해 오름차순 정렬이 되어 30이 맨 앞에 있는 것을 볼 수 있다.

 

위와 같은 방법으로 계속 진행한다.

queue에서 가장 작은 두 수 30, 60을 빼서 더한 후 queue에 넣으면 위와 같다.

sum에 30과 60을 더한다. (sum = 120)

 

 

다음 단계(설명 생략)

(sum = 283)

(sum = 537)

이제 queue의 size가 1이 되므로 while문을 빠져나온다.

 

[예제의 정답은 537]

 

 

System.out.println(sum);

4. 정답을 출력한다.

 

 

코드

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		PriorityQueue<Integer> queue = new PriorityQueue<>();
		
		int N = Integer.parseInt(st.nextToken());
		for(int i=0; i<N; i++) {
			queue.add(Integer.parseInt(bf.readLine()));
		}
		
		if(N == 1) {
			System.out.println(0);
			return;
		}
		
		int sum = 0;
		while(true) {
			if(queue.size() == 1) break;
			
			int num1 = queue.poll();
			int num2 = queue.poll();
			
			sum += num1 + num2;
			queue.add(num1 + num2);
		}
		
		System.out.println(sum);
	}
}

 

 

 

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