[백준] 1715 카드 정렬

시간복잡도 생각해보기

• N이 10^5 이므로, O(NlogN)에 끝내야한다.

풀이 아이디어

• 최소끼리 더하면 최소가 된다는 그리디적 상상을 해야한다.
• 더해준 최솟값 합도 다시 더 해줘야 하므로 우선순위 큐에 넣어서 항상 최소상태 유지
• 예를 들어 1,1,1,5 일때 1+1 을 하면 2가 되는데, 2,1,5가 아닌 1,2,5가 되어야 한다.
• 더한 배열을 업뎃하고 정렬해주는 식으로 하면 메모리 초과가 난다.

의사코드 / 풀이 과정

• 배열을 받아서 우선순위 큐에 넣는다.
• 가장 최소인 것들을 front에서 꺼내서(poll) 두개를 더한다.
• 더해준 값들도 우선순위 큐에 다시 넣는다. (add)

for(int i=0; i<N-1; i++) {
  Integer a = pq.poll();
  Integer b = pq.poll();
  Integer sum = a+b;
  answer += (sum);
  pq.add(sum);
}

틀린 코드

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

public class BJ1715 {
    static Integer arr [];
    public static void main(String [] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        arr = new Integer [N];
        for(int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(arr);
        long answer=0;
        for(int i=0; i<N-1; i++) {
            arr[i+1] =arr[i] + arr[i+1];
            answer+= arr[i+1];
            Arrays.sort(arr);
        }
        System.out.println(answer);
    }
}

메모리초과, 시간 초과
정렬을 계속해주니까 O(N^2) -> 극복방법: 우선 순위 큐

반례

6
1
1
1
1
100
100

[2, 1, 1, 100, 100] -> 원래 [1, 1, 2, 100, 100] 가 되어야 함.
일때 내 코드대로라면 계속해서 최소상태를 보장해주지 않지만, 우선순위 큐를 사용하면 o(logN)으로 최신상태를 보장해준다.

---

우선순위 큐는 왜 항상 정렬이 O(logN)일까

큐는 먼저 들어오는 데이터가 나가는 FIFO 형식의 자료구조이고, 우선순위 큐는 이런 큐를 우선순위 대로(숫자의 크기 등등) 정렬해놓은 자료구조다.

우선순위 큐는 일반적으로 힙을 이용해 구현한다. 

 

힙(Heap)

힙이란 우선순위 큐를 위해 고안된 완전 이진트리 형태의 자료구조다.

여러 개의 값 중 최대값이나 최솟값을 찾아내는 연산이 빠르다.

힙의 특징 

힙은 부모노드와 서브트리간 대소 관계가 성립된다. 

이진트리와 달리 중복된 값을 허용한다.

힙의 종류

최대 힙

최대 힙은 부모 노드의 키 값이 자식 노드보다 크거나 같다.

최소 힙

최소 힙은 부모노드의 키 값이 자식 노드보다 작거나 같은 완전 이진 트리이다.

 

우선순위 큐 구현 방식

우선순위 큐는 힙 뿐만 아니라 배열이나 연결 리스트로도 가능하다.

하지만 배열, 연결리스트는 선형 구조이므로 O(N)의 삽입 삭제 가 걸린다.

힙은 삽입, 삭제를 하면서 계속 힙의 성질을 유지하려고 하기 때문에 삽입 삭제할 때 계속 깊이 탐색을 한다. 따라서 (logN)의 삽입과 삭제가 걸린다.

예를 들어 

이런 경우에는 요소개 총 9개이고 깊이는 2^>=9 를 만족하는 최소 n이 4이기 때문이다. 따라서 깊이는 4이다.

깊이는 따라서 log2의 N이라고 한다

 

우선순위 큐 = PriorityQueue

자바에서는 우선순위 큐를 이렇게 정의한다.

static PriorityQueue<Integer> pq = new PriorityQueue<>();

 

 

---

출처: https://suyeon96.tistory.com/31