99클럽 코테 스터디 14일차 TIL, 프로그래머스 / 징검다리

🔑 오늘의 학습 키워드 : 이분 탐색

🔗 문제링크 https://school.programmers.co.kr/learn/courses/30/lessons/43236

 

def solution(distance, rocks, n):
    left = 0
    right = distance
    rocks.sort()
    rocks.append(distance)
    while left <= right:
        mid = (left + (right - left) // 2)
        prev = 0
        removed = 0
        for rock in rocks:
            if rock - prev < mid :
                removed += 1
            else :
                prev = rock
            if removed > n:
                break
        if removed > n:
            right = mid - 1
        else :
            left = mid + 1
    return left-1

 

🗒️ 공부한 내용 본인의 언어로 정리하기

🤔 문제를 보고 든 생각

distance가 10 ^ 9 인거 보면 일반적으로 풀면 안되고 특별한 생각을 해야겠다는 것을 느낄 수 있다.

 

이번 문제는 구하라고 하는 것이 두 징검다리의 최소길이의 최대값이다.

 

그렇다면 이분탐색을 통해 최소 길이에 얼만큼 바위를 뽑는지를 알아보면 된다.

⏰ 예상 시간 복잡도 O(nlogn (정렬)+ log (distance))

2 log 5 * 10 ^ 5  + 9

제한 사항

제한사항
도착지점까지의 거리 distance는 1 이상 1,000,000,000 이하입니다.
바위는 1개 이상 50,000개 이하가 있습니다.
n 은 1 이상 바위의 개수 이하입니다.

 

😎 알고리즘 개요

예를 들면 n이 7일때

 

최소길이 3 -> 5개 뽑음

최소길이 4 -> 5개 뽑음

최소길이 5 -> 6개 뽑음

최소길이 6 -> 7개 뽑음

 

-> 6 return 

 

이런 식으로 최소길이에 대해 몇개가 뽑히는지를 알아내면서 이분 탐색을 하면 된다.

 

그러면 1부터 distance까지 거리에서 최소길이(answer)에 n개가 뽑히는 지 알 수 있다.

 

✅ 오늘의 회고

- 이분 탐색의 경계 조건에 대해 잘 알아야 한다.

- 제한 조건을 파악하여 해당 문제의 알고리즘을 유추할 수 있어야 한다.

 

#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL