[백준 1715] 카드 정렬하기- java (solved.ac - 골드 4)

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

1715번: 카드 정렬하기

풀이

문제를 보았을 때 알 수 있는 힌트

문제를 보았을때 핵심으로 보아야할 것이 몇가지가 존재한다.

1. 정렬된 두 묶음의 숫자 카드가 존재함.

2. 두 묶음을 합치면 한 묶음이 되는데 두 묶음의 합이 된다.

3. 이렇게 여러개의 묶음을 합치면 합의 증가하게 된다.

4. 이때 최소한 몇 번의 비교가 필요한지 구하여라.

간단하게 접근하면 최소인 값 두개를 묶고 정렬을 하고 다시 최소인 값 두 개를 묶고 정렬.. 이를 반복한다.

하지만 하나를 정렬하기 위해서 반복을하는 것은 시간적으로 손해가 존재한다.

그렇기에 자동으로 정렬을 할수있고 최소값을 꺼낼수있는 우선순위 큐를 사용하면 쉽게 풀 수 있는 문제이다.

여기서 1번을 조심해야하는데 1개밖에 없다면 비교를 몇번해야할까? 이미 정렬이 되어있기때문에 0번이 된다.

이점을 고려해서 문제를 풀면 쉬운 문제이다.

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

public class Main {
	static int n,sum;
	static PriorityQueue<Integer> q = new PriorityQueue<>();
	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		for (int i = 0; i < n; i++) {
			q.add(Integer.parseInt(br.readLine()));
		}
		if(q.size()==1) {
			sum = 0;
		}
		else {
			while(q.size()>1) {
				int a = q.poll();
				int b = q.poll();
				sum+=a+b;
				q.add(a+b);
			}
		}
		System.out.println(sum);
	}// end main

}

https://github.com/dydwkd486/coding_test/tree/main/baekjoon/java/baekjoon1715

GitHub - dydwkd486/coding_test: 코딩테스트 공부한 내용 정리