Java 백준 문제풀이 (58) 1715 _ 카드 정렬하기

 

간만에 마음에 평온이 찾아오는 쉬운 문제다.

우선 문제를 읽고 분석해보자.

 

 

        // 카드 묶음 비교
        // 최소한의 비교 횟수 구하기
 
        // 10 20 40인 경우
        // ( 10 + 20 ) = 30
        // ( 30 + 40 ) = 70
        // => 100
 
        // ( 10 + 40 ) = 50
        // ( 50 + 20 ) = 70
        // => 120
 
        // => 작은 묶음부터 비교하는 것이 효율적이다

 

그렇다.. 간단한 조건이라 길게 설명할 부분은 없다.

중요한 부분은 "작은 묶음부터 비교하는 것이 효율적이다"라는 부분이다.

 

문제 어디에서도 카드 묶음을 순차적으로 주겠다는 말을 한 적이 없기 때문에 잊지 말고 정렬을 해줘야 한다.

위의 조건에 맞춰서 야매 수도코드를 작성해봤다.

 

 

 

 

 

public class Main {
    public static void main(String[] args) throws Exception {
        // 카드 묶음 비교
        // 최소한의 비교 횟수 구하기
 
        // 10 20 40인 경우
        // ( 10 + 20 ) = 30
        // ( 30 + 40 ) = 70
        // => 100
 
        // ( 10 + 40 ) = 50
        // ( 50 + 20 ) = 70
        // => 120
 
        // => 작은 묶음부터 비교하는 것이 효율적이다
 
 
        // 카드 묶음 수 N 입력 받기
        // 반복문 ( i < N )
            // 카드 배열[i] = 카드카드~
 
        // 배열 정렬
 
        // greedy(카드 배열)
 
        // 출력 정답
        }
 
        // greedy(카드 배열)
        // int answer = 0;
        // 누적합 배열 만들기
        // answer += 누적합배열[i]
        /// return answer;
    }
    }

 

음.. 정말 심플하군.

늘 그렇듯 글을 쓰면서 풀고 있어서 이게 맞는지 틀렸는지 나도 모른다.

아마 딱히 틀릴만한 부분이 없는 것 같다.

 

 

.

 

 

라고 생각했는데 풀어보니 약간의 문제가 있다.

위 방법으로도 정답을 맞출 수는 있지만 코드가 다소 지저분해진다.

이유는 주어지는 값이 1개인 경우를 고려해야하기 때문이다.

 

조금 더 깔끔하게 풀 수 있는 방법이 없나 싶어 검색해보니 정석은 우선순위 큐를 이용하는 방법이다.

우선순위 큐를 이용해서 풀어보자.

정답은 아래에.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;
 
public class Main {
    public static void main(String[] args) throws Exception {
        // 카드 묶음 비교
        // 최소한의 비교 횟수 구하기
 
        // 10 20 40인 경우
        // ( 10 + 20 ) = 30
        // ( 30 + 40 ) = 70
        // => 100
 
        // ( 10 + 40 ) = 50
        // ( 50 + 20 ) = 70
        // => 120
 
        // => 작은 묶음부터 비교하는 것이 효율적이다
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        Queue<Integer> queue = new PriorityQueue<>();
 
        for (int i=0; i<N; i++) {
            queue.add(Integer.parseInt(br.readLine()));
        }
 
        int answer = 0;
 
        while (queue.size()>1) {
            int card1 = queue.poll();
            int card2 = queue.poll();
 
            int sum = card1 + card2;
            answer += sum;
            queue.add(sum);
        }
 
        System.out.println(answer);
    }
}