[백준] 1715 : 카드 정렬하기 - JAVA

Benjamin·2023년 1월 9일

BAEKJOON

목록 보기

35/70

🙋🏻‍♀️그리디 알고리즘 사용!

문제분석

처음에 선택하는 데이터셋의 크기가 작은것이 중요하다.
따라서 카드 묶음 크기를 오름차순으로 정렬한 후, 가장 작은것 2개를 선택해서 합치고, 합친것을 다시 배열에 넣은 후 오름차순으로 재정렬하고... 이 과정을 원소가 1개 남을때까지 반복한다.

즉, 데이터의 삽입, 삭제, 정렬이 자주일어나므로 우선순위 큐를 이용해야한다.

슈도코드

N입력받기
우선순위큐 pq선언
int sum 
for(N만큼 반복) {
	pq에 카드 크기 입력받기
}
while(pq.size() >1) {
	sum += 가장 앞 2개 빼서 더하기
	pq.add(sum)
}

Troubleshooting

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

public 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<Integer> pq = new PriorityQueue<>();
		for(int i=0; i<N; i++) {
			pq.add(Integer.parseInt(br.readLine()));
		}
		int sum = 0;
		while(pq.size() > 1) {
			int first = pq.poll();
			int twice = pq.poll();
			sum = sum + first + twice;
			pq.add(sum);
		}
		System.out.println(sum);	
	}
}

문제

백준에서 '틀렸습니다'를 받았다.

원인

sum은 현재까지 비교한 누적횟수이다.
카드 묶음 2개를 더한게 pq에 그때그때 계속 들어가야하는데, first + twice + first + twice +. .. (즉 sum)을 pq에 넣으면 값이 중복돼서 들어가는것이다.

해결

pq.add(sum); -> pq.add(first + twice); 수정

제출코드

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

public 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<Integer> pq = new PriorityQueue<>();
		for(int i=0; i<N; i++) {
			pq.add(Integer.parseInt(br.readLine()));
		}
		int sum = 0;
		while(pq.size() > 1) {
			int first = pq.poll();
			int twice = pq.poll();
			sum = sum + first + twice;
			pq.add(first + twice);
		}
		System.out.println(sum);
	}
}