[java 백준] 골드 4/ 1715번 카드 정렬하기

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

1715번: 카드 정렬하기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
class Main {
 
    public static int n;
    public static int cnt;
 
    public static class Item implements Comparable<Item>{
        int item;
 
        public Item(int item){
            this.item=item;
        }
 
        @Override
        public int compareTo(Item other){
            return this.item- other.item;
        }
    }
 
    public static PriorityQueue<Item>queue=new PriorityQueue<Item>();
 
 
 
 
/*
1
 
1
 
최소 비교 횟수는 0회입니다.
 */
 
 
    public static void main(String args[]) throws NumberFormatException, IOException {
 
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
 
        n=Integer.parseInt(br.readLine());
 
        for(int i=0;i<n;i++){
            queue.add(new Item(Integer.parseInt(br.readLine())));
 
        }
 
        if(queue.size()==1){
            cnt=0;
        }
 
        else{
            while(!queue.isEmpty()){
 
                if(queue.size()==1){
                    int node=queue.poll().item;
 
                    cnt+=node;
 
                }else if(queue.size()>=2){
                    int node1=queue.poll().item;
                    int node2=queue.poll().item;
                    int node3=node1+node2;
 
                    cnt+=node3;
 
                    if(queue.size()!=0){
                        queue.add(new Item(node3));
                    }
 
                }
 
            }
        }
 
        System.out.println(cnt);
 
 
 
 
 
 
 
    }
 
}
 

 

우선순위 큐를 활용해서 카드들을 오름차순으로 정렬한다면 최소 비교횟수가 만들어질거다.

큐에서 카드를 두개씩 뽑아서  더한 값을 cnt에 누적합시켜주고 큐에 남아있는 원소가 있을때만  큐에 다시 넣어준다.

큐에 남아있는 원소가 없다면 계산을 다 수행한 것이다!

 

만약 큐에 남은 원소가 한개라면 그 땐 그냥 원소한개만 빼줘서 cnt에 넣어주면 된다.

 

⭐ 결정적으로 놓친부분

만약 n이 1이라면 비교할 수 있는 횟수가 없기에 0을 출력해야 했다. 그래서 초기 큐의 크기가 1인것과 아닌 것을 분류해서 코드를 짰다! (99%에서 틀렸습니다가 나오는 진귀한 경험을 해보았다)

 

https://www.acmicpc.net/board/view/33201

글 읽기 - 채점중 99%에서 틀렸습니다 뜨는데 이유가 뭘까요?