백준 14247 나무자르기 - JAVA

문제 및 입출력 + 테케

해당 문제를 풀 때 다음과 같이 접근했다.

1. 매일 매일 산에 오를 때마다 가장 큰 것을 자르면 어떨까? -> 테케에 맞지 않는다.

2. 나무가 자라는 게 등차 수열이네 -> 그러면 공차의 오름차순 대로 나무를 잘라볼까? -> 테케 맞음

3. 그러면 오름차순 정렬할 때 Arrays.sort를 쓸까? 

4. 어차피 계속 배열을 유지할 필욘 없으니 PriorityQueue를 써볼까?

라는 의식흐름에서 나온게 다음과 같은 코드이다.

-> 하지만 함정이 숨어 있었다...흑흑

 

다름아닌 데이터 타입... 

최악의 상황을 가정해 보았다.

나무 100,000개에  등차가 10,000이고 첫항이 전부 100,000 일 경우 

99999*100000/2*10000 + 100000  = 49,999,500,100,000 => long으로 선언해야함 

long = +-9,223,372,036,854,775,807 / int +- = 2,147,483,647 이므로 long 타입으로 total 변수를 선언했어야 했다.

 

소스코드는 우선순위큐(최소힙)과 배열로 푼 방식 둘다 구현해봤다.

삼성 SW 역량 테스트 B형을 치른지 3일? 됐는데 아직 자료구조, 데이터 타입의 중요성을 까먹은 것인가?
설계에 더욱 더 공을 들이자! 
항상 최악의 경우를 테스트 해보자!

package boj;

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

public class Boj_14247 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		long total = 0; 
		// 나무 100,000개에 공차가 10,000이고 첫항이 전부 100,000 일 경우   99999*100000/2*10000 + 100000  = 49,999,500,100,000 => long으로 선언해야함 
		// long = +-9,223,372,036,854,775,807, int +- = 2,147,483,647
		
		// 배열, 연결리스트로 구현한다면 삭제 O(1), 삽입(n)
		// 우선순위 큐의 경우 삭제, 삽입 O(log2n); n= 100000기준 32
		// Arrays.sort의 경우 dualPivotQuicksort : 평균 O(nlogn) 최악:O(n^2) 100000 기준 평균 1600000
		// Collections.sort의 경우 Timsort :  평균 O(nlogn) 최악:O(n^2) n = 100000 기준 평균 1600000
		// 한 번의 정렬을 하여 사용하여야 하며 데이터가 지속적으로 필요하지 않으므로 우선순위 큐를 사용한다.
		
		PriorityQueue<Integer> pq = new PriorityQueue<>();
		StringTokenizer stz = new StringTokenizer(br.readLine());
		
		// 각 나무의 상수 부분은 미리 더해줘도 된다. 결국 공차의 오름차순 대로 나무를 자르게 될 것이다.
		for (int i = 0; i < n; i++) {
			total += Integer.parseInt(stz.nextToken());
		}
		stz = new StringTokenizer(br.readLine());
		
		for (int i = 0; i < n; i++) {
			pq.add(Integer.parseInt(stz.nextToken()));
		}
		
		// 우선순위 큐의 경우 객체 생성시 Collections.reverseOrder()을 파라미터로 넘겨주면 내림차순으로 정렬된다.
		for (int i = 0; i < n; i++) {
			total += i*pq.poll(); // 첫째날부터 자른다고 한다면 n은 0부터 시작한다.
		}
		
		System.out.println(total);
		
		
		// 배열 version
		
		int tree[] = new int[n];
		StringTokenizer stz2 = new StringTokenizer(br.readLine());
		
		// 각 나무의 상수 부분은 미리 더해줘도 된다. 결국 공차의 오름차순 대로 나무를 자르게 될 것이다.
		for (int i = 0; i < n; i++) {
			total += Integer.parseInt(stz2.nextToken());
		}
		stz2 = new StringTokenizer(br.readLine());
		
		for (int i = 0; i < n; i++) {
			tree[i] = Integer.parseInt(stz2.nextToken());
		}
		Arrays.sort(tree);
		
		for (int i = 0; i < n; i++) {
			total += i*tree[i]; // 첫째날부터 자른다고 한다면 n은 0부터 시작한다.
		}
		
		System.out.println(total);
		
		
		
	}
}