백준 1715번 자바 ☆

문제

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

1715번: 카드 정렬하기

 

1. 우선순위 큐

우선순위 큐를 알기전에 큐라는 자료구조를 먼저 알아야한다.

 

큐는 선입선출(FIFO) 형태의 자료구조이다. 먼저 들어오면 먼저 나간다.

음료를 먹을 때 빨대를 생각하면 쉽다. 먼저 빨아들인 음료가 내 입속으로 먼저 온다.

 

그럼 우선순위 큐가 뭔지 짐작이 간다. 큐는 큐지만 우선순위가 있는 큐다.

그냥 구현을 하게 되면 오름차순으로 정렬이 된다. 해당 문제에 그대로 적용하면 된다.

 

2. 접근 방식

처음엔 누적합 방식으로 접근했다. 누적합을 배열에 저장한 후 첫번째 원소를 제외한 나머지 원소들의 합이 정답이라고 생각했다.

 

하지만 누적합을 진행하다 보면 값이 기존 원소보다 커지는 경우가 생기는데 이 부분 때문에 틀렸다.

예를 들어 아래와 같은 배열이 있을 때 원소들의 누적합 과정을 보자

7

12

123

234

234

455

456

876

887

998

7 + 12 = 19
19 + 123 = 142
142 + 234 = 376
376 + 234 = 610
610 + 455 = 1065
1065 + 456 = 1521

 

빨간색 글씨가 잘못된 구간이다.

누적합을 하면서 가장 작은 원소 2개를 더해야 하는데 순차적으로 누적합을 진행해 문제가 생겼다.

 

그래서 우선순위 큐를 사용해 가장 작은 원소 2개를 뽑아 더해 나가야한다.

물론 위와 같은 방식에서 조건문을 걸어 for문을 여러번 돌리면 해결할 수도 있겠지만 올바른 해법은 아닌듯 하다.

 

3. 구현

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

public class Main1715 {

	static int N;
	static int[] cards;
	static PriorityQueue<Long> pq;
	static long sum;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		cards = new int[N];
		pq = new PriorityQueue<Long>();
		for (int i=0; i<N; i++) {
			pq.add(Long.parseLong(br.readLine()));
		}
		
		while (pq.size() > 1) {
			long temp =  pq.poll() + pq.poll();
			sum += temp;
			pq.add(temp);
		}
		System.out.println(sum);
	}
}

 

정리 : 평소 우선순위 큐 자료구조를 잘 사용하지 않아서 생소했다. 익숙해지도록 노력하자.