[Do It! 코딩테스트 자바편(김종관)] 문제 033(백준: 1715번)

난이도

이해하기 쉽고 간단했다. 하지만 우선순위 큐 말고 구간 합으로 풀 수 있지 않을까 해서 시도했는데 틀렸다.

왜 그런지 이유를 찾아보려고 디버그 해봐도 못 찾겠다…

문제

카드 정렬하기(백준: 1715번)

풀이(우선순위 큐 / 맞음)

import java.util.PriorityQueue;
import java.util.Scanner;

public class test {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt(); // 카드 묶음의 수 저장
    PriorityQueue<Integer> pq = new PriorityQueue<>();
    for (int i = 0; i < N; i++) {
      int data = sc.nextInt();
      pq.add(data);
    }
    int data1 = 0;
    int data2 = 0;
    int sum = 0;
    while (pq.size() != 1) {
      data1 = pq.remove();
      data2 = pq.remove();
      sum += data1 + data2;
      pq.add(data1 + data2);
    }
    System.out.println(sum);
  }
}

풀이(구간 합 / 틀림)

import java.util.Arrays;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int a[] = new int[n];
    for (int i = 0; i < n; i++) {
        a[i] = sc.nextInt();
    }
    Arrays.sort(a);

    int sum[] = new int[n];
    for (int i = 0; i < n; i++) {
        if (i == 0)
            sum[i] = a[i];
        else
            sum[i] = sum[i - 1] + a[i];
    }

    int ans = 0;
    if (n != 1) {
        for (int i = 1; i < n; i++)
            ans += sum[i];
    }
    System.out.println(ans);
  }
}

=> 아래의 데이터 셋을 넣었을 때 다른 출력이 나왔지만 이유는 아직 모르겠다…

10
123
456
234
998
12
7
876
887
455
234

• 우선순위 큐 코드: 12108
• 구간 합 코드: 13696