📖 문제

📝 풀이과정

• 우선 바위들을 출발지점에서 가까운 순서로 정렬해서 최솟값을 이분탐색을 통해 찾는 방법을 선택했다.
• 이분탐색을 하는 과정 속에서 각 지점 사이 거리들을 검사할 때 선형적인 방법을 채택했다. <- 바위는 많아 봤자 50000개이기 때문에 시간초과가 나지 않는다.
• 구하고자 하는 값 : 바위를 제거하고 각 지점 사이의 거리의 최솟값 중 가장 큰 값
• 각 지점 사이의 거리의 최댓값은 distance(출발지점 ~ 도착지점)이기 때문에 이분탐색을 위한 시작값은 0, 끝값은 distance로 두었다.
• 이분 탐색 과정에서는, 각 지점 사이의 거리를 담은 리스트인 dists를 순회한다.
  1. 현재까지 돌을 제거해서 합쳐진 거리가 m보다 작으면 돌을 제거
  2. m보다 크면 돌을 제거하지 않고 현재 돌부터 시작해서 새로 다시 거리를 계산(합쳐진 거리 = 0)
     2-1. 이때 돌을 제거해야 하지만 더이상 돌을 제거할 수 있는 횟수가 남아있지 않다면?
            -> m이 최솟값이 된다는 가정에 모순이 생긴다!! m의 값을 줄인다.
     2-2. 돌도 원하는 횟수만큼 제거했고 m이 최솟값인 조건도 만족한다면?
            -> 일단 정답의 후보가 될 수 있으므로 정답을 담는 변수에 넣어놓고 m값을 높인다.

⌨ 코드

def solution(distance, rocks, n):
    # 바위들이 있는 위치가 출발지점으로부터 가까운 것 순으로 정렬한다.
    rocks.sort()
    
    # 출발지점, 도착지점, 바위 간의 거리를 담는 리스트 dists 구성
    # dist[i] : i ~ i+1 사이 거리
    dists = []
    for i in range(len(rocks) + 1):
        # 출발지점 ~ 첫 바위 사이 거리
        if i == 0 : 
            dists.append(rocks[i])
        # 마지막 바위 ~ 도착지점 사이 거리
        elif i == len(rocks):
            dists.append(distance - rocks[i - 1])
        # 바위 간의 거리
        else:
            dists.append(rocks[i] - rocks[i - 1])

    # 이분 탐색을 위한 시작값, 끝값 설정
    i, j = 0, distance

    # 이분 탐색 시작
    # m : 각 지점 사이의 거리의 최솟값
    # tmp_n : 앞으로 제거할 수 있는 돌의 개수
    # tmp_distance : dp~dq 사이 거리 -> m을 넘어가면 새로 초기화
    # isOk : m이 조건을 만족하는지 여부를 담는 변수
    while i <= j:
        m = (i + j) // 2
        tmp_n = n
        tmp_distance = dists[0]
        isOk = True
        
        # 각 지점 사이의 거리를 담은 list 순회
        for d in range(1, len(dists)):
            # 현재까지 돌을 제거하면서 합쳐진 거리가 m보다 작으면 -> 돌을 제거해야하는 상황
            if tmp_distance < m:
                # 돌을 제거하는 횟수가 안남았다면
                if tmp_n == 0:
                    isOk = False
                    break
                # d - 1번째 돌과 d번째 돌 사이에 있는 바위 삭제
                tmp_n -= 1
                tmp_distance += dists[d]
            else:
                # tmp_distance를 d번째 돌 ~ d+1번째 돌(혹은 끝) 사이 거리로 초기화해준다.
                tmp_distance = dists[d]
                
        # m이 각 지점 사이의 최솟값이라는 것을 만족한다면
        if isOk:
            answer = m # 일단 정답에 넣어놓고
            i = m + 1 # 좀 더 큰 수가 또 각 지점 사이의 최솟값이 될 수 있는지 확인
        else:
            j = m - 1           
    return answer

☺ 느낀점

나는 이분 탐색을 하면서 이전 바위와 현재 바위 사이 거리를 구하는 것까지 생각하면 머리가 깨질 것 같아서 미리 각 지점 사이 거리를 담는 리스트를 따로 두어서 문제를 풀었는데 대부분의 사람들은 제때제때 거리를 계산해서 문제를 풀었다. 막상 그 코드들을 보니 내 풀이가 훨씬 복잡하다는 것을 느꼈다...😢나는 쪼개놓은 것을 다시 붙여가면서 계산을 한거고, 다른 사람들은 이미 다 붙여져있는 것을 index만 옮겨가면서 계산을 해준 것이었다.
또, 나는 돌을 제거해야하는 상황인데 돌 제거 횟수가 모자른 경우를 미리 걸러내기 위해서 isOk라는 변수를 새로 만들어서 처리해주었는데, 다른 사람들은 일단 최솟값을 만족시키는 데에만 집중해서 최솟값을 만족시키도록 돌을 제거할 수 있는 만큼 다 제거해놓고 나서 나중에 제거한 바위의 개수가 n보다 큰지 작은지 판단해서 m값을 갱신시켰다. 음... 결론적으로 나는 (돌 제거 횟수 + 최솟값) 모두를 동시에 생각하려고 했고 다른 분들은 (최솟값)만 일단 따지고 본 것이기 때문에 후자가 훨씬 생각하기도 편하고 코드도 보기 좋고 깔끔했다. 물론 내 코드보다 연산은 조금 더 많이 하겠지만... 시간 복잡도에 영향을 미치는 정도는 아니니까 ㅎ.ㅎ...
요즘 내가 문제에 주어진 조건을 맞추는 데에 집착을 해서 다른 사람들에 비해서 문제를 복잡하게 푼다는 것을 많이 느낀다. 문제를 너무 가까이서 보지 말고 좀 멀리서 바라보고 내가 좀 더 쉽게 풀 수 있는 방향을 먼저 생각해보는 연습이 필요하다.