[백준] 단계별로 풀어보기(단계:21,이분 탐색,JAVA)2110번, 공유기 설치

문제 링크

2110번: 공유기 설치

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이분 탐색이란 오름차순으로 정렬된 값들에서 특정한 값을 찾는 과정입니다.

중간 값을 임의의 값으로 설정하여 찾는 값과 비교하여 동일하면 찾는 값이 되고 크면 시작값이 임의의 값이 되고 작으면 최대값이 임의의 값이 되어 그 과정을 반복하여 찾는 값이 정렬된 값에 존재하는지 확인하는 방법입니다.

이분탐색에 자세한 내용은 링크를 남기겠습니다.

이진 검색 알고리즘 - 위키백과, 우리 모두의 백과사전

예를들어(시작값 = 1, 최대값 = 9)

찾는 값 = 3, 중간값 = 5

1. 찾는 값이 중간 값보다 작으므로 최대값은 4가 된다.

1

2

3

4

5

6

7

8

9

시작값 = 1, 최대값 = 4 찾는값 = 3 중간값 = 2

2. 찾는 값이 중간 값보다 크므로 시작값은 = 3

1

2

3

4

5

6

7

8

9

시작값 = 3, 최대값 = 4 찾는값 = 3 중간값 = 33. 찾는 값과 중간값이 같으므로 3은 정렬된 숫자에 존재합니다.

1

2

3

4

5

6

7

8

9

이 문제에서는 공유기 설치 거리에 따른 이분 탐색을 이용해서 얻은 중간값의 거리만큼 공유기를 설치했을 때 설치해야하는 공유기의 개수 만족하는지를 확인하는 것이 문제에 핵심입니다.

이분 탐색으로 저장된 집들의 위치를 오름차순으로 정렬해주어야 합니다.

 

공유기를 설치하는 거리의 범위는 첫 번째집과 마지막 집에 따라 달라지기 때문에 최대값으로 설정하였습니다.

예제입력1에서는 공유기를 설치할 수 있는 최소 거리는 1, 최대 거리는(첫 번째집 위치 - 마지막집 위치 + 1) 9-1+1 = 9으로 1~9가 범위가 됩니다.

 

여기서 자를 수 있는 높이의 최대값이므로 UpperBound를 구하는 공식을 사용할 것입니다.

UpperBound는 아래 문제에서 End로 표현하는 것을 참고하시면 감사하겠습니다.

[백준] 단계별로 풀어보기(단계:21,이분 탐색,JAVA)10816번, 숫자 카드 2

 

그래서 1~9 범위에서 이분탐색으로 중간값을 얻어서 집들 사이에 중간값 거리만큼 공유기를 설치할 때 설치해야되는 공유기 수가 나오는지 확인하는 것을 반복하여 공유기 최대 거리를 얻어내는 것입니다.

 

예제입력1으로 진행되는 과정을 살펴보겠습니다.

공유기 설치할 수 있는 집들 사이의 최대길이 = 9(9-1+1), 최소 길이 = 1

1

~

9

1. 중간값은 (1+9)/2 = 5입니다.

집 사이간 거리가 5보다 크거나 같으면 공유기를 설치해보겠습니다. 

여기서 첫 번째 집에는 공유기를 무조건 설치한다고 봅니다.

1		= 공유기설치
2	2-1=1	= 설치X
4	4-1=3	= 설치X
8	8-1=7	= 공유기설치
9	9-8= 1	= 설치X

설치된 공유기는 2개로 설치되야할 공유기 3개보다 작으므로 집 사이간 공유기 설치 거리가 줄어들어야 합니다.

그래서 자를 수 있는 줄어든 거리의 범위는 최대길이 = 5, 최소길이 = 1

1

~

5

2. 중간값은 (1+5)/2 = 3입니다.

집 사이간 거리가 3보다 크거나 같으면 공유기를 설치해보겠습니다.

동일하게 첫 번째 집은 공유기가 설치됩니다.

1		= 공유기 설치
2	2-1=1	= 설치x
4	4-3=3	= 공유기 설치
8	8-4=4	= 공유기 설치
9	9-8=1	= 설치X

설치된 공유기의 개수와 설치해야될 공유기의 개수가 같습니다.

 

여기서 결과를 도출하는 것이 아닌 문제에서는 공유기 수를 만족하면서 가장 인접한 거리의 최대 거리를 구해야하기 때문에 이제부터는 최대로 설치할 수 있는 거리를 구합니다.

3보다 더 긴 거리를 설치하는 범위는 최대길이 = 3, 최소길이 = 4

4

~

3

3. 이분탐색에서는 start<end가 유지될 때까지 반복되기 때문에 다음에 이분탐색은 진행하지 못하므로써 설치할 공유기 수를 만족하면서 인접한 거리가 가장 큰 4가 출력됩니다.

하지만 UpperBound로 구현하였기 때문에 마지막에 -1을 취해야 해서 4-1 = 3으로 3이 최대 인접한 거리라고 결과를 출력할 수 있습니다.

 

문제를 해결한 알고리즘의 과정입니다.

1. 집 사이간 공유기 설치 가능한 거리에 최대값을 구하였습니다.

2. 범위(1 ~ 처음 집 위치 - 마지막 집 위치+1)에서 중간값을 구합니다.

3. 중간값을 통해 공유기를 설치해보고 필요한 개수만큼 설치되는지 확인합니다.

4. 필요한 개수가 나오면 중간값보다 더 큰 범위로, 나오지 않는다면 작은 범위로 이분탐색을 진행합니다.

5. 위 과정을 반복하여 최소길이가 최대길이보다 커졌을 때 최소길이-1를 반환합니다.

 

※중간값 구하는 공식 = (시작값 + 최대값) / 2

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 이용하여 N과 C을 나누었습니다.
• 최대값 이분탐색/거리당 공유기 설치 개수를 구하는 houseDistance,routerCheck함수를 만들었습니다.
• 함수를 실행 후 BufferedWriter에 공유기 설치 최대 거리를 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• houseDistance함수에서 이분탐색에 UpperBound를 사용하여 최대값을 구하였습니다.
• routerCheck함수에서 중간값의 거리만큼 공유기를 설치했을 때 설치할 수 있는 개수를 구하였습니다.

 

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	static int[] house;		//집 위치좌표 저장 배열
	static int N;		// 집의 개수
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        //--------입력값 저장 및 배열 초기화---------
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        N = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());
        house = new int[N];
        for(int i=0;i<N;i++)
        	house[i] = Integer.parseInt(br.readLine());
        Arrays.sort(house);		//오름차순 정렬
        //-------함수 실행 및 결과 출력---------
        bw.write(houseDistance(1, house[N-1] - house[0] + 1, C) + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
    //----------UpperBound를 이용한 이분탐색 함수---------
    public static int houseDistance(int start, int end, int C) {
    	while(start<end) {
    		int median = (start + end)/2;
    		if(routerCheck(median)<C)
    			end = median;		//UpperBound로 median으로 변경
    		else
    			start = median + 1;
    	}
    	return start-1;		//UpperBound로써 -1을 취해줌
    }
    //-------공유기 설치 가능 횟수 구하는 함수---------
    public static int routerCheck(int median) {
    	//첫 번째 집 공유기 설치했다는 설정--------
    	int count = 1;
    	int lastLocation = house[0];
        //--------설치 가능 공유기 횟수 구하기------
    	for(int i=1;i<N;i++) {
    		int location = house[i];
    		if(location - lastLocation >= median) {
    			count++;
    			lastLocation = location;
    		}
    	}
    	return count;
    }

}