[백준] 카드 정렬하기 / 자바

문제         

https://www.acmicpc.net/problem/1715

레벨: G4
알고리즘: 그리드
풀이시간: 1시간
힌트 참조 유무: 무

1 번째 시도   

• 오름차순 정렬 필요
• 두가지 생각이 들었습니다. 정렬 후
  • 1. 두 묶음씩 묶어서 계속 더해가며 줄일 것인가
  • 2. 1 번째와 2 번째만 계속 더해가며 줄일 것인가
• 예시를 들어 비교
  • 1 3 5 10
    
    4 + 15 + 4 + 15 = 38
    
    4 + 4+5 + 9 +10 =32 
• 결론: 2 번째 방법 선택 

// 3, 5킬로그램 봉지가 있다.
// 최대한 5킬로그램 봉지를 많이 들고가야 한다.
// 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.

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

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[] numbers = new int[N];
        for(int i = 0; i < N; i++) {
            numbers[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(numbers);

        int answer = numbers[0] + numbers[1];
        int pre = numbers[0] + numbers[1];
        for(int i =2; i < N; i++) {
            answer += pre + numbers[i];
            pre = pre + numbers[i];
        }

        System.out.println(answer);

    }
}

첫 번째 입력 값에서는 잘 나오지만 예외상황을 캐치하지 못한 것 같다.

 

2 번째 시도  

• 알고리즘을 잘못 짰다.
• 10 10 10 10 10 10 10 10일 때
  (10+10) +(10+10) +(10+10) +(10+10) = 80
  (20 + 20) + (20 + 20)   = 80
  40 + 40 = 80
  
  답: 240이지만, 내방식대로 하면 350이 나온다.
• 이 문제에서 중요한 건 큰 숫자가 가장 적게 합쳐지는 것이다. 
• 가장 작은 숫자 2개를 합치고 우선순위 큐에 넣고 다시 가장 작은 숫자 2개를 합치는 과정 반복

// 3, 5킬로그램 봉지가 있다.
// 최대한 5킬로그램 봉지를 많이 들고가야 한다.
// 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.

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

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<Long> priorityQueue = new PriorityQueue<>();
        for (int i = 0; i < N; i++) {
            priorityQueue.add(Long.parseLong(br.readLine()));
        }
        Long answer = 0L;
        while (priorityQueue.size() > 1) {
            Long smallest1 = priorityQueue.poll();
            Long smallest2 = priorityQueue.poll();
            Long result = smallest1 + smallest2;
            answer += result;
            priorityQueue.add(result);
        }
        System.out.println(answer);

    }
}

배운점

• 삽입하고 정렬된 값을 뽑길 원한다면 우선순위 큐 사용하기
  • 우선순위 큐 =  느슨한 정렬 상태
• 문제에서 입력 범위 보고 int인지 long인지 판별하기