[프로그래머스] 징검다리

https://programmers.co.kr/learn/courses/30/lessons/43236

코딩테스트 연습 - 징검다리

 

 

< 문제 설명 >

출발지점부터 도착지점까지의 거리는 distance이고,

두 지점 사이에 rocks의 위치에 바위가 존재한다.

바위중에 n개를 제외한 바위 사이의 거리가 최대일 때, 그 거리를 출력하라.

 

 

< 문제 이해 >

바위의 개수는 1~50000개이기 때문에 두개를 제외하는 경우를 다 따지게 되면

너무 많은 연산을 하게된다. 이럴 때는 이분탐색을 사용한다.

돌과 돌 사이의 거리를 이분탐색으로 찾으면 된다.

이때, 거리에 따른 바위의 개수를 구해 바위의 개수가 len(rocks)-n보다 크면 거리를 늘리고

작으면 거리를 줄이면 된다.

 

 

< 문제 풀이 >

def solution(distance, rocks, n):
    rocks.sort()			# 이분탐색을 하기 위해서는 정렬 필수
    rocks.append(distance)		# 도착지점을 리스트에 추가
    
    start = 1				# 출발지점
    end = distance			# 도착지점
    while start <= end:
        mid = (start+end)//2
        prerocks = 0			# 이전 위치. 처음엔 출발지점(0)
        cnt = 0				# 돌의 개수 카운트
        for r in rocks:
            if r-prerocks >= mid :	# 돌과 돌 사이의 거리가 mid보다 크거나 같으면
                cnt += 1		
                prerocks = r		# 이전 위치를 현재 돌의 위치로 변경
        
        if cnt >= len(rocks)-n:		# 돌의 개수가 len(rocks)-n보다 크거나 같으면
            start = mid + 1
        else:				# 돌의 개수가 작으면
            end = mid-1
    
    return start-1

 

 

 

 

예전에 백준 이분탐색으로 풀었던 문제들과 비슷하다.

이것도 풀어보면 좋을 듯!

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