[백준] JAVA 자바 : 카드 정렬하기 (1715번)

---

그리디 알고리즘 파트에서 처음 맞이하는 골드 단계 문제이다.
문제 자체는 어렵진 않은데... 나는 몇 시간을 헤맸다...ㅋㅋㅋ

입력된 정수 배열을 처음부터 끝까지 돌면서 가장 작은 값 두 개를 빼서 sum에 더한 후, 크기에 맞게 배열에 다시 넣어주면 된다.
여기서 난 처음에 배열에서 값을 뺀 후에 일일이 Arrays.sort()로 정렬을 해줬었는데, 그래서 계속 메모리초과 + 시간초과가 떴다... 결국 못 참고 아래의 '알고리즘 분류'를 봤는데 우선순위 큐가 있네??

 

그래서 우선순위 큐를 사용해주면 쉽게 정렬을 유지한 채로 요소의 삽입과 삭제가 가능해진다!
우선 순위 큐는 이번에 처음 써보는데... 새로 하나 배워간다...!

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

public class SortingCard {

    public static int stoi(String str) {
        return Integer.parseInt(str);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PriorityQueue<Integer> pQ = new PriorityQueue<>();
        
        int N = stoi(br.readLine());
        int[] array = new int[N];
        for (int i=0; i<N; i++) {
          pQ.offer(stoi(br.readLine()));
        }
        
        int sum = 0;
        for (int i=0; i<N-1; i++) {
          int tmp = pQ.poll() + pQ.poll();
          sum += tmp;
          pQ.offer(tmp);
        }
        
        System.out.println(sum);
    }
}

 

로그인