[백준] #2805. 나무 자르기 (실버 2)

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

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		int[] trees = new int[n];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) {
			trees[i] = Integer.parseInt(st.nextToken());
		}

		Arrays.sort(trees);

		int low = 0;
		int high = trees[n-1];
		int maxHeight = 0;

		while (low <= high) {
			int mid = (low+high) / 2;
			int total = 0;

			for (int tree : trees) {
				if (tree > mid) {
					total += tree - mid;
				}
			}

			if (total >= m) {
				maxHeight = mid;
				low = mid + 1;
			}  else {
				high = mid - 1;
			}
		}
		System.out.println(maxHeight);

	}
}

 

st = new StringTokenizer(br.readLine());의 사용에 대해 헷갈렸음

 

위의 코드로 인텔리제이에서 예시 입력값을 입력하여 실행 시에는 성공했지만
백준에 제출 시 실패하였음!

▼ ▼ ▼ ▼ ▼

주어질 입력값의 범위

• 나무의 수 N 범위 : 1 ≤ N ≤ 1,000,000
• 나무의 길이 M 범위 : 1 ≤ M ≤ 2,000,000,000
• 나무의 높이 : 1,000,000,000보다 작거나 같은 양의 정수 또는 0

→ total의 자료형을 int가 아닌 long으로 설정했어야함!!!
(int의 범위 : -2,147,483,648부터 2,147,483,647)

 

+) 위의 코드에서처럼 나무의 길이가 저장된 배열을 정렬하지 않아도 결과와 관계없기 때문에 Arrays.sort(trees);를 사용하지 않고
     배열에서의 최대값만 찾아내 저장하여 high값으로 사용하였음!

 

최종 코드

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		int[] trees = new int[n];
		st = new StringTokenizer(br.readLine());
		int maxTreeHeight = 0;
		for (int i = 0; i < n; i++) {
			trees[i] = Integer.parseInt(st.nextToken());
			if(trees[i] > maxTreeHeight){
				maxTreeHeight = trees[i];
			}
		}

		int low = 0;
		int high = maxTreeHeight;
		int maxHeight = 0;

		while (low <= high) {
			int mid = (low+high) / 2;
			long total = 0;

			for (int tree : trees) {
				if (tree > mid) {
					total += (tree - mid);
				}
			}

			if (total >= m) {
				maxHeight = mid;
				low = mid + 1;
			}  else {
				high = mid - 1;
			}
		}
		System.out.println(maxHeight);

	}
}