[코딩테스트] 백준(BAEKJOON) - 카드 정렬하기(Java, 1715번)

안녕하세요~ 또 문제를 풀기위해 오늘도 왔습니다.

 

평일에 글을쓰는건 또 오랜만이네요~

다 저의 게으름 때문이기에 변명의 여지는 없습니다 ㅠㅠ

 

그럼 문제 바로 만나보겠습니다.

 

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

1715번: 카드 정렬하기

 

네~ 카드 정렬하기라는 문제입니다.

사실 이 문제는 계속 틀려서 풀이를 보고 풀었습니다.

 

정말 간단한 원리인데 이부분을 생각 못했더군요~

코드입니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.StringTokenizer;


public class Main {
		public static void main(String[] args) throws NumberFormatException, IOException {
			
			Scanner sc=new Scanner(System.in);
			
			PriorityQueue<Long> queue=new PriorityQueue<>();
			
			int time=sc.nextInt();
			
			for(int i=0;i<time;i++)
			{
				long number=sc.nextInt();
				queue.add(number);
			}
			long sum=0;
			long answer=0;
			
			while(queue.size()>1)
			{
				sum=queue.poll()+queue.poll();
				answer+=sum;
				queue.add(sum);
			}
			
			System.out.print(answer);	
			
			
	}

}

 

하나씩 알아보시죠~

 

먼저 제가 생각한 핵심원리는

- 최소의 합을 계속 만들어야한다

- 그렇기에 PriorityQueue를 통해 최소의 수로 정렬한다. 입니다.

 

PriorityQueue<Long> queue=new PriorityQueue<>();

- PriorityQueue는 카드 뭉치들을 저장할 Queue입니다.

 

			for(int i=0;i<time;i++)
			{
				long number=sc.nextInt();
				queue.add(number);
			}

- 다음은 카드 묶음들을 queue에 집어 넣겠습니다.

 

			while(queue.size()>1)
			{
				sum=queue.poll()+queue.poll();
				answer+=sum;
				queue.add(sum);
			}

- 아마 여기부분이 핵심 부분이 될 것 같네요

① queue.size가 1이라면 더이상 섞을 카드뭉치가 없기에 종료 합니다.

② 다음은 문제에서와 같이 최소의 카드 묶음 두 쌍을 섞기위해 더해줍니다.

③ 저에게는 이 부분이 핵심이었습니다. 저는 더한 값을 그대로 다시 재활용 했었는데

더한 카드 묶음또한 다시 Queue에 넣어 정렬이 되도록 해야합니다.

 

이렇게 풀어내시면 해당 문제 해결하실 수 있겠습니다.

 

감사합니다. 이번 문제 간단하셨을까요?

 

그럼 이만 마무리 하겠습니다.

감사합니다. 😊😊