[백준 1715] 카드 정렬하기 (JAVA)

백준 1715번 문제  - 카드 정렬하기

1715번: 카드 정렬하기

---

문제 분석

 

• 모든 카드를 합치기 위해 사용되는 합치는 최소 횟수를 구하고 출력해라.

---

해결 키 포인트

 

• 그리디 알고리즘 사용
  • 가장 작은 수들끼리 먼저 합치는 것이 이 문제의 핵심
• 하지만, 시간도 메모리도 여유롭지 않다
  • List 사용 - 메모리, 시간 초과
  • ArrayList 사용 - 시간 초과
  • 뽑아내고 넣고 정렬하고의 반복으로 메모리, 시간 초과가 난다
• 우선순위 큐 사용으로 메모리, 시간을 최소화한다.

 

---

그리디 알고리즘 (탐욕 알고리즘)

 

현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘이다.

 

쉽게 말해, 지금의 최선 = 전체의 최선

 

뒤에 사진에서 서울에서 부산까지의 최소거리를 구하고자할 때, 
서울에서 대구의 최솟 값을 선택하고, 대구에서 부산까지의 최솟값을 선택하는 알고리즘

 

파이썬 알고리즘 인터뷰 (나무위키)

 

---

코드

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

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

        // N 입력
        int N = Integer.parseInt(br.readLine());

        // 카드 묶음 입력
        PriorityQueue<Integer> cards = new PriorityQueue<>();
        
        for(int i=0;i<N;i++) {
            cards.add(Integer.parseInt(br.readLine()));
        }

        int count = 0;

        // 카드 큐에 남은 카드가 1개보다 작아질 때까지
        while(cards.size() > 1) {
            // 두가지 카드를 뽑아 합쳐 새로운 카드 생성 (우선순위 큐로 인해 가장 작은 두 수가 뽑힌다)
            int newCard = cards.poll() + cards.poll();
            
            // 해당 카드를 count에 추가하고, 다시 카드 큐에 추가
            count += newCard;
            cards.add(newCard);
        }

        System.out.println(count);
    }
}