프로그래머스 Lv4- 징검다리

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

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

 

1) 문제 분석

• 출발지점~ 도착지점 까지의 거리가 distance만큼 떨어져 있으며, 그 사이에 바위들이 놓여있다. 이 바위들이 놓여져 있는 지점을 rocks라는 배열에 저장한다.
• 그중 바위를 n개 만큼 제거하는데, 각 경우에서 각 지점 사이 거리의(출발, 끝지점 포함) 최솟값이 가장 큰 값을 return하도록 한다.

2) 코드

def solution(distance, rocks, n):
    answer = 0
    start, end = 0, distance
    rocks.sort()

    while start <= end:
        mid = (start+end)//2
        current, cnt = 0,0

        for rock in rocks:
            diff = rock - current #현재 돌과 이전에 남은 돌 사이의 거리 계산
            if diff < mid:
                cnt += 1 #돌 제거 횟수 +1
            else:
                current=rock # 제거하지 않고 남겨두는 돌 

        if cnt > n:
            end = mid-1
        else:
            start = mid+1
            answer = mid

    return answer

 

3) 문제 풀이 과정

• 바위 사이 거리의 최솟값은 1, 최댓값은 시작지점과 도착지점 사이의 거리인 distance이다.
• 1~distance 사이의 범위에서 돌 사이 거리의 최솟값 x를 임의로 지정하였을때, 이 최솟값은 n개의 돌을 제거하였을 때 성립하는가? 를 찾아야 한다.
• 이 최솟값의 값을 임의로 중간 지점(mid)로 잡았을때, 이 거리가 돌 사이의 거리의 최솟값이어야 하므로, 돌사이의 거리를 계산해서 해당 거리가 중간값보다 작을 때에는 제거한다.
  • 이때 돌을 제거한 횟수가 주어진 횟수 n보다 같거나 작다면 돌을 더 제거할 수 있는 경우이므로 돌 사이의 거리가 더 멀어질수 있고, 거리의 최솟값은 증가해야 한다.
  • 그러나 돌을 제거한 횟수가 주어진 횟수 n보다 많다면 돌 사이에 발생할 수 있는 거리의 최솟값은 이것보다 작아지기 때문에, 이 값은 감소해야 한다.
• 여기서 이분탐색의 method를 적용할 수 있는데, 처음에는 시작지점 start를 1로, 도착지점 end를 distance로 잡고, 첫 최솟값으로 지정된 중간지점 mid를 (start+end)/2로 지정한다.
  • 먼저 돌 사이의 거리를 측정하여 이 값이 거리의 최솟값 mid보다 작으면 돌을 제거하고, mid보다 크면 돌을 그대로 둔다. 이때 돌을 제거한 횟수를 저장해두어야 한다.

  while start <= end:
          mid = (start+end)//2
          current, cnt = 0,0
  
          for rock in rocks:
              diff = rock - current #현재 돌과 이전에 남은 돌 사이의 거리 계산
              if diff < mid:
                  cnt += 1 #돌 제거 횟수 +1
              else:
                  current=rock # 제거하지 않고 남겨두는 돌 
  

  • 이때 배열 한바퀴를 돌며 돌 사이의 거리를 모두 잰 후,
  • 돌 제거 횟수 ≤ n 이라면 돌을 더 제거 할수 있거나, mid를 변경해 다른 돌을 제거하여 돌 사이의 거리가 더 멀어질 수 있다는 의미이다.
    • 따라서 최솟값 mid를 더 크게 지정해야 하므로, answer를 mid에 저장하고, start point를 mid+1로 지정한다.
  • 돌 제거 횟수 > n 이라면 돌을 덜 제거해야 하므로 돌 사이의 거리가 더 가까워져야 한다는 의미이다.
    • 따라서 mid를 더 작게 지정해야 하므로 end point를 mid-1로 지정한다.

  if cnt > n:
              end = mid-1
          else:
              start = mid+1
              answer = mid
  

  • 이를 start > end가 될 때까지(이분탐색이 끝나는 조건) while 문에 넣고 돌린다.
• 시간 복잡도는 n ( 돌 배열 한바퀴 돌면서 거리 측정) * log n (이분탐색) = nlogn