[java] 문제 033 (백준 1715)

문제

카드 정렬하기

 

교재 풀이

import java.util.PriorityQueue;
import java.util.Scanner;

public class P1715_카드정렬하기 {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt(); // 카드 묶음의 수 저장
    PriorityQueue<Integer> pq = new PriorityQueue<>();
    for (int i = 0; i < N; i++) {
      int data = sc.nextInt();
      pq.add(data);
    }
    int data1 = 0;
    int data2 = 0;
    int sum = 0;
    while (pq.size() != 1) {
      data1 = pq.remove();
      data2 = pq.remove();
      sum += data1 + data2;
      pq.add(data1 + data2);
    }
    System.out.println(sum);
  }
}

 

내 풀이) 24.6.18에 풀고 틀림

import java.util.*;
import java.io.*;

public class Main
{
	public static void main(String[] args) throws IOException{
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        PriorityQueue<Integer> pq=new PriorityQueue<>();
        
        for(int i=0;i<n;i++){
            pq.add(sc.nextInt());
        }
        
        int ans=0;
        int size=pq.size()-1;
        for(int i=0;i<size;i++){
            if(i==0){
                int e1=pq.remove();
                int e2=pq.remove();
                int tmp=e1+e2;
                ans+=tmp;            
            }else{
                int e=pq.remove();
                int tmp=ans+e;
                ans+=tmp;
            }
        }
        
        System.out.println(ans);

	}
}

    // n이 주어짐
    //     n은 십만보다 작음
    //     n개의 숫자 카드 묶음
    // 그 다음 n개의 줄에 카드 묶음 각각의 크기 주어짐 
    //     카드 묶음 크기는 1000 이하인 양의 정수
    // 출력은 최소한 몇 번의 비교가 필요한지
    
    // 접근법
    //     일단 이게 그리디임을, 또 우선순위 큐를 사용함은 알고 있음
    //     카드 크기 각각을 우선순위 큐에 넣어주고 
        
    //     큐에서 최솟값이 제일 fornt에 있을 텐데
    //     front 두 묶음의 크기를 더하고 
    //     ans에 +=30
    //     그리고 다시 ans와 그 다음 front 더하고 
    //     이를 더하고 다시 ans+=front 
    //     그렇게 큐가 다 비워지면 
        
    //     ans를 출력
    // 슈도코드
    //     n 입력: n은 숫자 카드 묶음 개수 
    //     우선순위 큐 pq: Integer 
        
    //     for n번 반복해서 
    //         우선순위 큐에 넣어줌 
        
    //     ans
    //     for pq.size-1만큼 반복 
    //         if i==0일 때
    //             꺼내고 꺼내고 
    //             더하고 
    //             ans에 추가하고 
    //         else 
    //             꺼내고 //40 
    //             ans와 더하고  // 30 + 40
    //             ans에 추가하고 // 30 + 70
        
    //     ans를 출력함

 

설명

24.6.18) 그러네, 꺼낸 카드 묶음 2개를 합친 건, 다시 우선순위 큐에 넣고, 다시 꺼내는 걸 반복해야 했네.