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

🔺 문제

1715번: 카드 정렬하기

 

🔺 코드

- 틀림

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];

        for(int i = 0 ; i < N ; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(arr);

        for(int i = 1 ; i < N ; i++) {
            arr[i] += arr[i-1];    
        }
        System.out.println(arr[arr.length - 2] + arr[arr.length - 1]);
    }
}

누적합 이용해서 풀 생각을 했었다만...

장렬한(?) 틀림..

 

 

 

- 정답

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int N = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> pq = new PriorityQueue<>();
 
        for(int i = 0 ; i < N ; i++) {
            int num = Integer.parseInt(br.readLine());
            pq.add(num);
        }
 
        int data1 = 0;
        int data2 = 0;
        int sum = 0;
 
        while(pq.size() != 1) {
            // 2개 카드 묶음을 큐에서 뽑음
            data1 = pq.remove();
            data2 = pq.remove();
 
            sum += data1 + data2;    // 2개 카드 묶음 합치는데 필요한 비교횟수, 결괏값에 더해 저장
            pq.add(data1 + data2);
        }
        System.out.println(sum);
    }
}

✅ 해결 아이디어
✔ 우선순위 큐 (∵ 데이터 삽입,삭제,정렬이 자주 일어나므로)
1. 현재 카드 개수가 가장 작은 묶음 2개 선택해 합침.
2. 합친 카드 묶음을 다시 전체 카드 묶음 속으로 넣기 (이 때, 우선순위 큐는 즉시 자동 정렬!)
3. 카드 묶음이 하나만 남을 때까지 반복

 

---

🔺 다른 풀이들

- 우선순위 큐 말고 배열 2개 사용하심

로그인

 

 

- 배열 한 개만 사용하심

로그인

로그인

---

💬 느낀 점

 

우선순위 큐

- FIFO (우선순위 높은 원소가 먼저 탈출)

- 데이터의 삽입·삭제·정렬 자주 발생 시 사용!

 

 

1회독	2회독	3회독	4회독	5회독
V	6/18

 

---

(참고)

✔ 우선순위 큐 클래스 사용법

[알고리즘] 우선순위큐(힙)는 왜, 언제 사용해야 할까

[Java] PriorityQueue(우선순위 큐) 클래스 사용법 & 예제 총정리

 

 

 

✔ Do it 알고리즘 코딩테스트 자바 편 (내돈내산)

Do it! 알고리즘 코딩 테스트 : 자바 편 : 네이버 도서