[JAVA] 2805번 - 나무 자르기
문제 탐색하기
- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하여 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정
문제를 풀기 위한 아이디어: 절단기 높이 h를 mid로 지정한다!!
문제에서 어떤 값에 따라 늘어나고 줄어드는 규칙이 있기 때문에 이분탐색을 쓰면 된다
높이h가 늘어나면 가져가는 나무의 미터m이 줄어든다.
높이h가 줄으들면 가져가는 나무의 미터m이 늘어난다.
그래서 절단기 높이 H를 mid값으로 정했다!!
이걸 떠올렸다면 나머지도 술술 풀수 있다
1. 이분탐색하는 while문 한개
2. 높이h에 따라 가져갈 수 있는 나무의 총합을 구하는 함수
이렇게 두 파트로 나눠서 생각하면 금방 풀 수 있다!
시간복잡도
일단 주어진 최대 수가 굉장히 크다. 높이는 최대 1,000,000,000이다. 모든 높이를 탐색하는건 1초안에 절대 불가능이다.
1. 이진탐색을 하려면 정렬이 되어있어야한다. 나무 n개 좌표 배열 정렬 -> O(N log N)
2. 이분 탐색: 나무 자르는 높이가 0에서부터 arr[arr.length-1]까지 가능하니까 이 사이에서 탐색한다. 최대 나무 높이를 H라고 하면, 이분 탐색은 O(logH)의 반복이 필요
3. 나무 총합 확인하는 함수: 주어진 mid높이에서 얻을 수 있는 나무의 총 양은 arr배열을 한번씩 확인해야하니까 O(n)이다
4. 총 시간 복잡도: O(nlogn+nlogH) =
코드 설계하기
위의 문제 탐색하기에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡았다면, 문제 풀이를 본격적으로 하기전, 문제를 풀이 위한 로드맵을 그려본다
어떤 순서로 코드를 작성해야 할지, 어떤 함수들을 작성해야 할지 등을 작성
1. 이분탐색
-> 높이에 따른 나무의 총합을 받아서 그게 m보다 큰지 작은지 판단해서, 탐색 범위를 조절해서 이분탐색을 실행한다!
while(start<=end) {
int mid = (start+end)/2;
long h = check(mid);
if(h>=m) {
ans = mid;
start = mid+1;
}
else {
end = mid-1;
}
}
2. 나무의 총 합 확인
private static long check(int length) {
long sum = 0;
for(int i=0; i<arr.length; i++) {
if(arr[i]>length) {
sum+=(arr[i]-length);
}
}
return sum;
}
시도 회차 수정 사항
- 무분별하게 "맞았습니다" 가 나올때까지 수정하는 형태의 문제 풀이를 반복하면, 내가 어떤 실수를 해서 해당 문제를 틀렸는지 모르게 된다
- 틀렸습니다를 받았다면 왜 틀렸는지 고민핸보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
1회차 시도
-> start변수를 arr[0]로 지정해서 오답
2회차 시도
-> true,false로 return값을 받아서 조건문을 처리했다. 모든 답이 0으로 나왔다.
while(start<=end) {
int mid = (start+end)/2;
if(check(mid)) {
ans = mid;
end = mid-1;
}
else {
start = mid+1;
}
}
System.out.println(ans);
}
private static boolean check(int length) {
int sum = 0;
for(int i=0; i<arr.length; i++) {
if(arr[i]>length) {
sum+=(arr[i]-length);
}
}
return sum>=m;
}
3회차 시도
-> 오버플로우 발생했다 정수 타입을 int에서 long으로 바꿈
12 2000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
정답코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeSet;
public class Main {
static int[] arr;
static int n,m;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
arr = new int[n];
st = new StringTokenizer(br.readLine());
for(int i=0; i<n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr);
int start = 0;
int end = arr[arr.length-1];
int ans = 0;
while(start<=end) {
int mid = (start+end)/2;
long h = check(mid);
if(h>=m) {
ans = mid;
start = mid+1;
}
else {
end = mid-1;
}
}
System.out.println(ans);
}
private static long check(int length) {
long sum = 0;
for(int i=0; i<arr.length; i++) {
if(arr[i]>length) {
sum+=(arr[i]-length);
}
}
return sum;
}
}