[백준] 2110번 공유기 설치

사용 언어 - PyPy3

2110번: 공유기 설치 (골드4, 이분 탐색)

문제 ★이분 탐색 문제★

2110번: 공유기 설치

python3으로는 시간 초과로 오답이지만, pypy3으로는 정답!

이분탐색은 while문으로 돌아가서 python보다 빠른 pypy3으로 했을 때만 정답이 나올 수 있다.

 

 

 

정답

집 좌표값의 차이를 start/end/mid 값을 지정하는 이분탐색 문제 !!

(코드 풀이)

1. 변수 선언

n 집의 개수

c 공유기의 개수

house 집 좌표값 리스트 -> 이분탐색 타겟이므로 sort()해주기!

집 좌표값 끼리의 거리를 확인해야하므로 집 좌표값의 차이를 start/end/mid 값으로 지정한다.

가장 가까운 거리는 1이기 때문에, start=1로 선언한다.

가장 먼 거리는 가장 먼 좌표값에서 가장 가까운 좌표값의 차이기 때문에, end = house[-1]-house[0] 로 선언한다.

결과값을 저장할 answer=0을 선언한다.

 

2. 이분 탐색 정의

mid는 start와 end의 중간값이다.

가장 가까운 집 좌표값부터 테스트해야하므로, current = house[0] 으로 시작해준다.

현재 테스트하는 대상 house[0]와 거리mid를 더한 값이 c-1개 만큼 나오는 지를 확인해야한다.

현재 위치에서 거리만큼 이동했을 때보다 크거나같은 집 좌표값이 있는지 확인한다.

 

거리를 mid로 두었을 때, 가능한 집의 개수를 cnt 변수로 세고, cnt가 c가 될 때까지 이분탐색을 진행한다.

가능한 집의 수가 cnt >= c 라면 start를 mid+1로, 가능한 집의 수가 cnt < c 라면 end를 mid-1로 갱신한다.

 

 

3. 출력

answer는 cnt >= c가 될때마다 mid로 저장된다.

가장 마지막에 저장한 mid 값이 정답이 된다.

# 정답 - 이분탐색

n, c = map(int,input().split())
house = []
for i in range(n):
    house.append(int(input()))

house.sort()
start, end = 1, house[-1]-house[0]
result = 0

while start <= end:
    
    mid = (start+end)//2
    current = house[0]
    cnt = 1
    
    for i in range(1,n):
        if house[i] >= current + mid:
            cnt += 1
            current = house[i]
        
    if cnt >= c:
        start = mid +1
        result = mid
    else:
        end = mid - 1

print(result)

 

---

레퍼런스

• 정답 참고

[백준] 2110 공유기 설치 파이썬 풀이

• 정답 깃허브

GitHub - yyeongeun/codingtest: 코딩테스트 공부

• pypy, python 언어차이

백준 문제 풀때, python3과 pypy3의 차이