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

사용 언어 - Python3

문제 - 징검다리

프로그래머스

 

정답

징검다리를 하나씩 건너면서 두 돌 사이의 거리를 찾는 이분 탐색 문제 (정답 맞춘 여부 X)

정답 풀이

1. start,end 정의

돌 사이의 최소 거리는 1, 최대 거리는 distance

2. rocks 오름차순 정렬

마지막 돌과 도착지점 사이의 거리도 있으므로, rocks 리스트에 distance를 추가해준다.

3. start <= end 일때까지 while 반복문 진행

del_stone 제거한 돌 개수

pre_stone 시작 돌 위치

3.1. 징검다리 하나씩 건너면서 for문 진행

rock 돌 위치와 pre_stone 시작 돌 위치를 비교

mid 값보다 작다면, 돌 한개 삭제

아니라면, 시작돌 위치를 rock으로 업데이트

삭제하려는 돌개수가 n개를 초과하면 break

3.2. start, end 범위 지정

del_stones>n인 경우, mid 값이 크기 때문이라 end = mid-1

아닌 경우, answer에 mid 값 입력한다. mid 값이 작기 때문이라 start = mid+1

# 정답
def solution(distance, rocks, n):
    answer = 0
    start, end = 1, distance
    rocks.sort() 
    rocks.append(distance)
    
    while start <= end: 
        mid = (start + end) // 2 
        del_stones = 0
        pre_stone = 0
        for rock in rocks:
            if rock - pre_stone <  mid:
                del_stones += 1 
            else:
                pre_stone = rock
            if del_stones > n:
            	break
                
        if del_stones > n:
            end = mid - 1
        else:
            answer = mid
            start = mid + 1
            
    return answer

---

레퍼런스

• 정답 참고

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

• 정답 깃허브

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