[코딩테스트 공부] 공유기 설치

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

문제 분석

우선 시간제한은 2초이다. 그런데 N이 200000까지 주어져있다. 따라서 NlogN의 복잡도로 구현을 해야함을 눈치챌 수 있다. 물론 이런 유형은 이분탐색으로 하는게 국롤이다

그런데, 일단 문제를 해석하는 것 부터가 쉽지않다. 가장 인접한 두 공유기 사이의 거리를 최대로 해라..? 이 문제를 읽고 내 심정은 정말 아래의 그림과 같았다...

정말 이 그림만큼 내 심정을 대변하는건 없을거다...

그래도 문제를 분석하다보면, 정말 의구심이 많이 든다. 내가 들었던 의구심은 이러했다.

• 이분탐색을 해야하는건 알겠는데, mid를 설정해도 mid만큼의 간격이 딱 떨어지는 경우가 없을 수도 있잖아..? 이건 어떻게 해야함?
• start, end를 조절하는 조건은 어떻게 해야함..? 막막하다.

사실 위에 적은 것보다 몇 배로 고민은 한 것 같다. 결과적으로 나는 이러한 결론에 도달했다.

일단 앞집부터 공유기를 계속 깔아보자. mid로 딱 떨어지지 않는 경우도 있겠지만, 딱 떨어지면 좋고, 아니여도 그냥 go하자.

그런데 이런 의문도 들 수 있다.

만약에 mid로 딱 떨어지는게 중간부터 등장하면 어떡할래?

그런데 첫 집부터 mid로 딱 떨어지지 않는 경우는, mid보다 큰 간격으로 두번째 집이 등장할 경우이므로, 위에서 생각한대로 진행해도 문제는 없을것이다!

이러한 생각으로 코드를 구성해보았다. 코드를 확인해보자!

코드를 확인해봅시다

import sys

# 2110번 문제
input = sys.stdin.readline

N, C = map(int, input().split())
coordinate_list = []

for _ in range(N):
    coordinate_list.append(int(input()))
    
coordinate_list = sorted(coordinate_list) # 정렬

start, end = 1, coordinate_list[N - 1] - coordinate_list[0]

# 탐색 시작
while start <= end:
    mid = (start + end) // 2
    count = 1
    current_house = coordinate_list[0]
    
    # 앞집에서 부터 공유기 심기
    for i in range(1, N):
        if coordinate_list[i] - current_house >= mid:
            count += 1
            current_house = coordinate_list[i]
            
    if count >= C:
        start = mid + 1
    else:
        end = mid - 1

print(end)

일단 입력받은 리스트를 정렬해줬다. 앞집부터 공유기를 깔아보기로 했기 때문이다.

그리고 start는 1, end는 첫 집과 끝 집의 거리 차로 정했다. 그리고 이분탐색을 돌면서 공유기를 첫 집부터 쫙 깔기 시작한다.

    mid = (start + end) // 2
    count = 1
    current_house = coordinate_list[0]

일단, 기본적인 아이디어는 과연 앞 집부터 공유기를 깔아서, C만큼의 집에 공유기를 깔 수 있을까? 를 체크해보자는 것이다. 만약에 깔지 못하면, 그거는 범위를 너무 넓게 잡았기 때문이고, 깔 수 있다면 범위를 조금 넓게 잡아도 괜찮다는 뜻일것이다!

    # 앞집에서 부터 공유기 심기
    for i in range(1, N):
        if coordinate_list[i] - current_house >= mid:
            count += 1
            current_house = coordinate_list[i]

current_house에는, 이전에 공유기를 심었던 집의 좌표가 저장되어있다. coordinate_list를 탐색하면서 mid보다 큰 간격을 가졌는지 검사를 하고, 조건을 만족하면 공유기를 심어주자는 것이다.

공유기를 다 심게되면, C의 조건에 따라서 start, end를 조절하면된다.

마지막으로, end를 출력하면 문제는 모두 해결된다!