문제 💁🏻♂️
해결 과정
이 문제는 파이썬 언어로 이미 풀어봤던 문제였다. 즉, 이미 이분탐색으로 풀리는 문제라는 것을 알고서 풀이를 시작했기 때문에 간단하게 문제를 해결할 수 있다는 자신감을 가졌다. 그러나, 끝없는 오답 판정을 받고야 말았다.
사고 과정 ❗️
이 문제는 K와 N의 범위를 보면 알 수 있듯이 시간복잡도 O(N^2) 이상으로는 절대 풀 수 없는 문제였다. 2중 for문을 활용한 브루트포스를 활용하게 되면 10^10 번의 탐색을 하기 때문에 TLE(= Time Limit Exceeded) 판정을 받을 것이다.
그렇다면 이 문제를 어떻게 해결하면 좋을까? 그것은 바로 이분탐색 방법이다. 이분탐색의 방법은 다음과 같다.
- 이분탐색을 하기 위해서 반드시 정렬이 되어있어야 한다. - O(NlogN)
- K개의 랜선들에 대해서 N개의 랜선을 만들 수 있는 랜선의 길이를 찾기 위해서 이분탐색을 실행한다. - O(logN)
- 정답을 반환한다.
위 단계처럼 정렬 + 이분탐색 시간 복잡도는 대략 (N + 1)*logN = O(NlogN)이다. 이 문제에서는 랜선의 길이가 최대 2^31 - 1 이므로, K개에 대해서 log(2^31 - 1)번 수행하기 때문에 약 10^5 * 31 = 3 * 10^6 이므로 문제를 충분히 풀 수 있다. 그렇게 생각한 대로 코드를 구현하고, 제출했더니 오답 판정을 받고 말았다. 왜 틀렸는지 도저히 모르겠어서 어떤 게시판 하나를 발견했다.
파이썬으로 풀 때에는 자료형의 범위를 따로 생각하지 않았지만, 자바 언어는 자료형의 범위 즉, int형 범위에 대해서 신경을 써줘야 함을 깨달았다. 이 문제에서는 mid = (left + right) / 2 라는 코드에서 int형 자료형인 left, right를 서로 더하고 2를 나누는 코드지만, left + right 자체가 int형 범위를 넘어 오버플로우가 일어난다면, mid에는 정말 이상한 값이 들어간다는 것을 깨달았다.
chatGPT가 친절하게 설명해주는 내용을 참고하자. 따라서, 이 부분만 모두 long 자료형으로 바꿔주고, 다시 제출하니 정답 판정을 받게 되었다! 이제는 자료형의 범위도 신경쓰면서 코테 문제를 풀어보자.
코드
오답 코드 (int)
import java.util.*;
import java.io.*;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int K, N, MAX = 1;
static int[] arr;
public static void main(String[] args) throws IOException {
st = new StringTokenizer(br.readLine());
K = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
arr = new int[K];
for (int i = 0; i < K; i++)
arr[i] = Integer.parseInt(br.readLine());
Arrays.sort(arr); // 이분 탐색을 위한 오름차순 정렬
int ans = bs();
System.out.println(ans);
}
private static int bs() {
int left = 1;
int right = arr[K - 1];
while (left <= right) {
int mid = (left + right) / 2; // mid: 가능한 랜선의 개수
long SUM = 0;
for (int num : arr)
SUM += (num / mid); // 랜선의 개수를 모두 더한다.
// 원하는 랜선의 개수와 같거나 많다면 -> 하한을 변경한다.
if (N <= SUM) {
// 랜선의 길이가 더 길다면 -> 갱신한다.
if (MAX < mid)
MAX = mid;
left = mid + 1;
// 원하는 랜선의 개수보다 적다면 -> 상한을 변경한다.
} else
right = mid - 1;
}
return MAX;
}
}
정답 코드 (long)
import java.util.*;
import java.io.*;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int K, N;
static long MAX = 1;
static int[] arr;
public static void main(String[] args) throws IOException {
st = new StringTokenizer(br.readLine());
K = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
arr = new int[K];
for (int i = 0; i < K; i++)
arr[i] = Integer.parseInt(br.readLine());
Arrays.sort(arr); // 이분 탐색을 위한 오름차순 정렬
long ans = bs();
System.out.println(ans);
}
private static long bs() {
long left = 1;
long right = arr[K - 1];
while (left <= right) {
long mid = (left + right) / 2; // mid: 가능한 랜선의 개수
long SUM = 0;
for (int num : arr)
SUM += (num / mid); // 랜선의 개수를 모두 더한다.
// 원하는 랜선의 개수와 같거나 많다면 -> 하한을 변경한다.
if (N <= SUM) {
// 랜선의 길이가 더 길다면 -> 갱신한다.
if (MAX < mid)
MAX = mid;
left = mid + 1;
// 원하는 랜선의 개수보다 적다면 -> 상한을 변경한다.
} else
right = mid - 1;
}
return MAX;
}
}Reference
