백준:1715 카드 정렬하기

풀이1

• list에 카드 묶음의 수를 저장한 후, 오름차순으로 정렬하고 하나씩 꺼내와 cardsAdd의 마지막 값과 더한 뒤, cardsAdd에 대입했다.
• 답으로 cardsAdd의 합을 대입했다.

결과 : 오답

두 카드묶음의 값을 더한 값이 남은 값(앞으로 더할 값)보다 큰 경우가 있기 때문에 오답이 나온 것 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

public class Problem1715 {
    static ArrayList<Integer> cards = new ArrayList<>();
    static ArrayList<Long> cardsAdd = new ArrayList<>();

    public static void main(String[] arg) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int lineNum = Integer.parseInt(br.readLine());

        for(int i = 0; i < lineNum; i++){
            cards.add(Integer.parseInt(br.readLine()));
        }

        //cards 배열을 오름차순으로 정렬
        Collections.sort(cards);

        //현재 인덱스의 값과 cardsAdd 리스트의 마지막 값을 더한 후 cardsAdd 리스트에 대입

        //첫 시행
        //N이 1인 경우 고려
        if(cardsAdd.isEmpty()){
            if(lineNum==1){
                cardsAdd.add(0L);
            } else {
                cardsAdd.add((long) (cards.get(0) + cards.get(1)));
            }
        }
        if(cards.size() > 2){
            for(int i = 2; i < cards.size(); i++){
                cardsAdd.add(cards.get(i) + cardsAdd.get(cardsAdd.size()-1));
            }

        }



        double sum = 0;
        for(long d : cardsAdd){
            sum += d;
        }

        System.out.println(sum);
    }
}

풀이 2

• 우선순위 큐에서 앞의 두 값을 뽑아 더한 뒤 다시 큐에 대입한다. 우선순위 큐는 항상 오름차순으로 정렬되기 때문에 앞의 두 개의 값이 가장 작은 두 개의 값이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;

public class Problem1715_2 {
    //오름차순 우선순위 큐
    static PriorityQueue<Long> cards = new PriorityQueue<>();
    static long sum = 0;

    public static void main(String[] arg) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int lineNum = Integer.parseInt(br.readLine());

        for(int i = 0; i < lineNum; i++){
            cards.add(Long.parseLong(br.readLine()));
        }

        //묶음이 하나가 아닌 경우
        if(lineNum != 1){
            //앞 두개씩 뽑아서 큐에 남는값이 하나가 될 때까지 개속 더하기
            while(cards.size() != 1){
                long firstCard = cards.poll();
                long secondCard = cards.poll();

                sum += firstCard + secondCard;
                cards.add(firstCard + secondCard);
            }
        }


        System.out.println(sum);
    }
}