[ 백준 - 2110 ] 공유기 설치

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

2110번: 공유기 설치

문제는 오늘이 3 번째 풀이인데 기존 코드를 보고 느낀점은 그래도 더 가독성이 좋아지지 않았나 싶다.

그리고 여러번 풀어서 그런지 불필요한 코드 없이 간결하게 짜여진 거 같아서 성장하는 기분이 든다.

---

[ 📌 풀이 ]

• 주어진 C개의 공유기는 반드시 설치 되어야 하는데, 첫 설치 공유기의 기준이 정해지지 않아서 항상 맨 앞에 있는 집에 설치
  • 맨 앞 or 맨 뒤는 풀이에 영향을 안주는 위치
• 집의 개수의 최대는 200,000 이고, 집 좌표의 최대 값은 1,000,000,000이기 때문에 나올 수 있는 최대 공유기 거리는 200000 x 1000000000 이기 때문에 단순 완전 탐색으로는 풀 수 없다.
• 이분 탐색으로 문제를 풀 때 특정 거리로 공유기 설치가 가능해도 멈추지 않고, 더 큰 거리도 가능한지 확인 해야 한다.

1) 주어진 거리 값으로 공유기 설치가 가능한지 확인

2 - 1) 가능: 더 큰 거리도 되는지 확인하기 위해서 거리 증가

2 - 2) 불가능: 공유기 설치가 가능한 거리를 찾기 위해서 거리 감소

3) 설치 가능한 거리중에서 가장 긴 거리 출력

---

[ 📌 코드 - Python (정글 과정 중 풀이) ]

import sys

N, C = map(int, sys.stdin.readline().split())
router_list = [] 

for _ in range(N):
    router_list.append(int(sys.stdin.readline()))

router_list.sort()
left, right = 0, router_list[-1] - router_list[0]
answer = 0

def binary_search():
    global left, right, answer
    
    while left <= right:
        mid = (left + right) // 2
        router_cnt = C - 1
        cur_router = router_list[0]

        for idx in range(1, N):
            dist = router_list[idx] - cur_router

            if dist >= mid:
                router_cnt -= 1
                cur_router = router_list[idx]

            if router_cnt == 0:
                break

        if router_cnt == 0:
            answer = mid

        if router_cnt > 0:
            right = mid - 1
        else:
            left = mid + 1
        
binary_search()
print(answer)

[ 📌 코드 - Python ]

"""
# Author    : Lee In Bok 
# Date      : 2023.12.26(Tue)
# Spend Time: 16m 24s
# Runtime   : 892 ms
# Memory    : 38848 KB
# Algoritm  : Binary Search
"""

import sys
inp = sys.stdin.readline

N, C = map(int, inp().split())
houses = [int(inp()) for _ in range(N)]
houses.sort()

l, r = 1, houses[-1]
max_dist = sys.maxsize

while l <= r:
  mid = (l + r) // 2
  cur_loc, cnt = 0, 1  # 현재 위치, 공유기 설치 수
  
  for idx in range(N):
    if houses[idx] - houses[cur_loc] >= mid:
      cnt += 1
      cur_loc = idx

  if cnt >= C:
    max_dist = mid
    l = mid + 1
  else:
    r = mid - 1

print(max_dist)

[ 📌 코드 - Java ]

/**
* Author    : Lee In Bok 
* Date      : 2023.12.26(Tue)
* Spend Time: 16m 24s
* Runtime   : 340 ms
* Memory    : 29908 KB
* Algoritm  : Binary Search
 */

package BaekJoon.BinarySearch.Q2110;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Q2110 {
  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 C = Integer.parseInt(st.nextToken());
     int[] houses = new int[N];
     
     for(int i = 0; i < N; i++){
       houses[i] = Integer.parseInt(br.readLine());
     }

     Arrays.sort(houses);
     int max = Integer.MAX_VALUE;
     int l = 1;
     int r = houses[N - 1];

     while(l <= r){
      int mid = (l + r) / 2;
      int cnt = 1;
      int cur_loc = 0;

      for(int i = 0; i < N; i++){
        if(houses[i] - houses[cur_loc] >= mid){
           cur_loc = i;
           cnt += 1;
        }
      }

      if(cnt >= C){
        l = mid + 1;
        max = mid;
      } else {
        r = mid - 1;
      }
    }

    System.out.println(max); 
  }
}

---

[ 📌 결과 - Python & Java ]

[ Result - Python & Java ]