[백준] 2110번 : 공유기 설치 - JAVA [자바]
https://www.acmicpc.net/problem/2110
2110번: 공유기 설치
첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가
www.acmicpc.net
- 문제
문제를 정확히 파악만 한다면 매우 쉬운 문제다.
- 알고리즘 [접근 방법]
그동안 숫자 카드, 랜선 자르기, 나무 자르기를 순서대로 풀어왔다면, 이 번 문제는 그리 어렵지는 않았을 것이다.
그럼에도 정답률이 낮은 이유라 한다면, 아마 이분탐색 구현을 제대로 하지 않았기 때문일 가능성이 매우 높지 않을까 생각을 해본다만.. 그렇기 때문에 필자가 이분 탐색 영역에서는 숫자카드 2 문제에서 다루었던 Upper Bound, Lower Bound 형식을 그대로 적용시키면서 최대한 코드 재사용성을 높이고자 같은 구조를 띄도록 노력하고 있다.
만약, 이 문제를 풀이하기 전에 이분탐색에 대해 조금이나마 헷갈리는 부분이 있다면 필자가 풀이한 숫자카드 2 문제를 한 번 보고 오시는 것을 추천드린다.
일단, 문제를 파악해보자.
이 문제의 주 된 목표는 어쨌건 N개의 좌표(집 위치)와 M개의 공유기를 설치해야 한다는 것이다.
다만, 최대한 설치되는 집 간의 거리를 벌릴 수 있게 만들고 싶을 뿐이다.
예로들어보자.
만약 다음과 같이 집이 위치한다고 가정해보자.
만약 최소 거리를 1이라고 가정하고 최대 설치할 수 있는 공유기의 개수는 몇 개일까?
다음과 같이 모든 집에 설치 할 수 있을 것이다. 왜냐하면, 집 간 거리가 모두 1 이상이기 때문이다.
그러면 최소 거리가 4일 때는 몇 개를 설치 할 수 있을까?
여기서부터 헷갈리는 부분일 수 있는데, 잘 생각해보면 쉽다. 포인트는 집 간 '최소 거리' 이상일 때 설치가 가능하다는 부분이다.
일단, 첫 번 째 집에 설치를 해보자.
그 다음, 다음 집을 탐색하면서, 이전의 설치 되었던 집과 거리를 계산해보면 4칸 떨어져있다. 즉, 설치 할 수 있다는 의미다.
위와 같이 두 번째 집에도 와이파이를 설치 할 수 있을 것이다.
그 다음을 보자.
직전에 설치 했던 두 번째 집과 세 번째 집 사이 거리는 3이다. 그러면 앞서 설정했던 최소거리 4보다 못미치기 때문에 공유기를 설치 할 수 없을 것이다.
위와 같이 세 번째 집은 건너뛰게 된다.
그 다음 탐색을 해보자.
직전에 설치 했던 집은 여전히 두 번째 집이다. 그리고 탐색 할 집은 네 번째 집이다. 그 사이의 거리는 딱 보더라도 설치가 가능해 보이듯 거리는 9로, 설치가 가능하다.
여기서 "왜 세 번째 집과 거리를 비교하는게 아니라, 직전에 설치했던 집과의 거리를 측정하나요?" 라고 궁금하실 수도 있다.
이 부분은 바로 다음에서 설명해보도록 하겠다.
같은 방식으로 다섯 번째 집은 설치를 할 수 없고, 가장 마지막 집에 채워지게 되면서 다음과 같이 될 것이다.
그러면 최소 거리가 4일 때 설치 가능한 공유기 개수는 4개임을 확인 할 수 있다.
자, 그러면 앞서 얘기 했던 "왜 세 번째 집과 거리를 비교하는게 아니라, 직전에 설치했던 집과의 거리를 측정하나요?" 에 대한 설명을 해야한다.
이는 너무나 당연한 것이지만, 다음을 생각해보면 매우 간단하게 왜 그래야하는지 알 것이다.
자, 한 번 모든 좌표에 집이 있다고 가정해보자. 그리고 최소 거리는 3 이라고 한다. 그러면 어떻게 해야할까?
그러면 상식적으로, 우리는 다음과 같이 설치 할 것이다.
위와 같이 총 8개의 공유기를 설치 할 수 있다.
그러나, 만약 직전에 설치했던 집의 위치와 거리를 비교하는 것이 아닌, 바로 이전의 집과 거리를 비교하게 되면 어떻게 될까?
그러면 첫 번째 집을 설치하고 난 뒤, 와이파이를 설치할 수 없게 되어버린다.
왜냐하면 당연하겠지만, 각 집 간의 거리는 모두 1이기 때문이다.
이러한 이유로 단순히 이전 집과의 거리가 아닌, 직전에 설치를 했던(가장 최근에 설치했던) 집과 현재 집과의 거리를 기준으로 판단해야 한다는 것이다.
문제의 메커니즘은 이해했다.
이제 이분탐색을 어떻게 적용해야 할지 고민을 해보자.
위 문제를 이해하면서 우리가 무엇을 기준으로 했을까? 바로 '거리'다. 최소 거리에 따라 설치할 수 있는 공유기의 개수가 달라진다라는 것을 확인 할 수 있었다.
결국 우리가 찾아야 하는 것은 '최소 거리에 대해 설치 가능한 공유기'가 문제에서 주어지는 '설치 해야 할 공유기의 개수(M)'와 같은 거리 중 최대로 가질 수 있는 '최소 거리'를 찾는 것이다.
정리하자면, 거리를 탐색 범위로 잡고 이분탐색을 하면서, 해당 거리에 대해 설치 가능한 공유기의 개수에 따라 탐색하는 거리의 범위를 좁혀나가면 된다는 것이다.
그리고, 찾아야 하는 것은 '최대로 가질 수 있는' 최소 거리이기 때문에 Upper Bound 형식을 따르면 된다는 것도 알 수 있다.
좀 더 쉽게 코드로 보자면 다음과 같다.
void main() {
while(lo < hi) { // Upper Bound 형식
int mid = (hi + lo) / 2;
/*
* mid 거리에 대해 설치 가능한 공유기 개수가 M 개수에 못미치면
* 거리를 좁혀야 하기 때문에 hi 를 줄인다.
*/
if(canInstall(mid) < M) {
hi = mid;
}
else {
/**
* 설치 가능한 공유기 개수가 M 개수보다 크거나 같으면
* 거리를 벌리면서 최소거리가 가질 수 있는 최대 거리를
* 찾아낸다.
*/
lo = mid + 1;
}
}
/*
* Upper Bound는 탐색 값을 초과하는 첫 번째 값을 가리키므로,
* 1을 빼준 값이 조건식을 만족하는 최댓값이 된다.
*/
System.out.println(lo - 1);
}
// distance에 대해 설치 가능한 공유기 개수를 찾는 메소드
int canInstall(int distance) {
// 첫 번째 집은 무조건 설치한다고 가정
int count = 1;
int lastLocate = house[0];
for(int i = 1; i < house.length; i++) {
int locate = house[i];
/*
* 현재 탐색하는 집의 위치와 직전에 설치했던 집의 위치간 거리가
* 최소 거리(distance)보다 크거나 같을 때 공유기 설치 개수를 늘려주고
* 마지막 설치 위치를 갱신해준다.
*/
if(locate - lastLocate >= distance) {
count++;
lastLocate = locate;
}
}
return count;
}
여기서 조심해야 할 것이 거리를 '줄이면' 설치 가능한 공유기 대수가 늘어나고, 거리를 '늘리면' 설치 가능한 공유기 대수가 줄어들 것이다.
즉, canInstall 메소드를 통해 얻은 공유기 대수가 M보다 작다면, 거리가 너무 길어서 설치 가능한 대수가 작다는 것이다. 그렇기 때문에 hi를 줄이는 것이고, 반대로 M보다 크거나 같다면 거리가 작다는 의미이므로 lo를 좁히는 것이다.
막상 짜고보면 코드가 진짜 짧다는 것을 볼 수 있다.
위를 토대로 코드만 작성해주면 된다.
- 2가지 방법을 사용하여 풀이한다.
항상 그래왔듯 Scanner 방식과 BufferedReader을 비교해보고자 한다.
1. Scanner + StringBuilder
2. BufferedReader + StringBuilder
- 풀이
- 방법 1 : [Scanner]
import java.util.Scanner;
import java.util.Arrays;
public class Main {
public static int[] house;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int M = in.nextInt();
house = new int[N];
for(int i = 0; i < N; i++) {
house[i] = in.nextInt();
}
Arrays.sort(house); // 이분탐색을 하기 위해선 반드시 정렬 되어있어야 한다.
int lo = 1; // 최소 거리가 가질 수 있는 최솟값
int hi = house[N - 1] - house[0] + 1; // 최소 거리가 가질 수 있는 최댓값
while(lo < hi) { // Upper Bound 형식
int mid = (hi + lo) / 2;
/*
* mid 거리에 대해 설치 가능한 공유기 개수가 M 개수에 못미치면
* 거리를 좁혀야 하기 때문에 hi 를 줄인다.
*/
if(canInstall(mid) < M) {
hi = mid;
}
else {
/**
* 설치 가능한 공유기 개수가 M 개수보다 크거나 같으면
* 거리를 벌리면서 최소거리가 가질 수 있는 최대 거리를
* 찾아낸다.
*/
lo = mid + 1;
}
}
/*
* Upper Bound는 탐색 값을 초과하는 첫 번째 값을 가리키므로,
* 1을 빼준 값이 조건식을 만족하는 최댓값이 된다.
*/
System.out.println(lo - 1);
}
// distance에 대해 설치 가능한 공유기 개수를 찾는 메소드
public static int canInstall(int distance) {
// 첫 번째 집은 무조건 설치한다고 가정
int count = 1;
int lastLocate = house[0];
for(int i = 1; i < house.length; i++) {
int locate = house[i];
/*
* 현재 탐색하는 집의 위치와 직전에 설치했던 집의 위치간 거리가
* 최소 거리(distance)보다 크거나 같을 때 공유기 설치 개수를 늘려주고
* 마지막 설치 위치를 갱신해준다.
*/
if(locate - lastLocate >= distance) {
count++;
lastLocate = locate;
}
}
return count;
}
}
가장 기본적인 방법이라 할 수 있겠다.
주석으로 이해하기 쉽게 하려다 보니 길어보일 뿐 실제 코드로는 진짜 몇줄 안되는 간단한 코드다.
- 방법 2 : [BufferedReader]
입력 방법을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다. 단, BufferedReader 는 문자열을 한 줄로 읽기 때문에 N과 M을 구분하기 위해 공백을 기준으로 문자열을 분리해주어야하니 StringTokenizer 을 사용하여 풀도록 하겠다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.Arrays;
public class Main {
public static int[] house;
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());
house = new int[N];
for(int i = 0; i < N; i++) {
house[i] = Integer.parseInt(br.readLine());
}
Arrays.sort(house); // 이분탐색을 하기 위해선 반드시 정렬 되어있어야 한다.
int lo = 1; // 최소 거리가 가질 수 있는 최솟값
int hi = house[N - 1] - house[0] + 1; // 최소 거리가 가질 수 있는 최댓값
while(lo < hi) { // Upper Bound 형식
int mid = (hi + lo) / 2;
/*
* mid 거리에 대해 설치 가능한 공유기 개수가 M 개수에 못미치면
* 거리를 좁혀야 하기 때문에 hi 를 줄인다.
*/
if(canInstall(mid) < M) {
hi = mid;
}
else {
/**
* 설치 가능한 공유기 개수가 M 개수보다 크거나 같으면
* 거리를 벌리면서 최소거리가 가질 수 있는 최대 거리를
* 찾아낸다.
*/
lo = mid + 1;
}
}
/*
* Upper Bound는 탐색 값을 초과하는 첫 번째 값을 가리키므로,
* 1을 빼준 값이 조건식을 만족하는 최댓값이 된다.
*/
System.out.println(lo - 1);
}
// distance에 대해 설치 가능한 공유기 개수를 찾는 메소드
public static int canInstall(int distance) {
// 첫 번째 집은 무조건 설치한다고 가정
int count = 1;
int lastLocate = house[0];
for(int i = 1; i < house.length; i++) {
int locate = house[i];
/*
* 현재 탐색하는 집의 위치와 직전에 설치했던 집의 위치간 거리가
* 최소 거리(distance)보다 크거나 같을 때 공유기 설치 개수를 늘려주고
* 마지막 설치 위치를 갱신해준다.
*/
if(locate - lastLocate >= distance) {
count++;
lastLocate = locate;
}
}
return count;
}
}
- 성능
채점 번호 : 36145493 - 방법 2 : BufferedReader
채점 번호 : 36145486 - 방법 1 : Scanner
- 정리
보면 문제에서 무엇을 찾고자 하는지만 정확히 파악하면 진짜 쉬운 문제임을 알 수 있다.
아마 이분 탐색 부분에서 많이 틀리는 이유가, 이분탐색 방식에 대한 반복문, 조건문 처리가 사람마다 다르다보니 제대로 자기만의 이분탐색 방식을 정확히 구축하고 있지 않는다면 탐색 과정에서 시간 초과가 걸리거나, 잘못 된 값을 반환하는 경우가 발생할 수 있게 된다.
그렇기 때문에 필자도 이분탐색을 포스팅하면서 최대한 탐색을 통해 범위를 좁히는 방식은 하나로 통일하여 풀이해주려고 하고있다.
여러분들도 이분탐색을 정확히 이해하고 자신만의 구현 틀을 잡아놓으면 이분탐색에서 보다 수월하게 문제를 풀이하실 수 있을 것이다.
여담으로, 근래 포스팅을 안한지 조금 오래되었다... (죄송합니다..) 나름 바쁜 사정이 있어 차마 손을 대고싶어도 점점 내용들은 복잡해지고, 길어져서 차마 건들일 수 없었는데, 어느정도 일이 마무리 되었기도 하고 앞으로 여유도 좀 더 있을 것 같아 다시 열심히 포스팅하여 좋은 내용으로 봽도록 노력하겠다. 그럼에도 꾸준히 방문해주셨던 분들에게 너무 감사할 따름이다.
만약 어렵거나 이해가 되지 않은 부분이 있다면 언제든 댓글 남겨주시면 최대한 빠르게 답변드리겠다.
'JAVA - 백준 [BAEK JOON] > 이분 탐색' 카테고리의 다른 글
| [백준] 12015번 : 가장 긴 증가하는 부분 수열 2 - JAVA [자바] (8) | 2022.04.25 |
|---|---|
| [백준] 1300번 : K번째 수 - JAVA [자바] (32) | 2021.12.27 |
| [백준] 2805번 : 나무 자르기 - JAVA [자바] (35) | 2021.09.12 |
| [백준] 1654번 : 랜선 자르기 - JAVA [자바] (37) | 2021.08.31 |
| [백준] 10816번 : 숫자 카드 2 - JAVA [자바] (47) | 2021.08.06 |