[Swift] 프로그래머스 징검다리 (with 쉬운 풀이 포함)



 

Problem

 

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

---

Solution

 

해당 문제는 이진탐색을 이용해서 풀어야 하는 문제입니다.

 

다리의 길이 n이라면 최소의 거리 중 가장 큰 값은 몇 일까요?

 

다리의 중간에 바위가 딱 한 개 있을 경우인 다리 길이의 절반, 즉, n/2 입니다.

 

고로 다리의 길이의 절반이 최소값 중 가장 큰 값이라고 시작합니다.

 

바위를 삭제해 나가면서 이 값을 만들 수 있는지 없는지를 확인해야 합니다.

 

문제에 나와있는 예제로 설명드리겠습니다.

 

다리의 길이: 25

바위의 위치: 2,14,11,21,17 -> 2, 11, 14, 17, 21

삭제해야 할 바위 갯수: 2

 

아래와 같이 바위가 있겠죠?

 

다리의 길이가 25이므로 기준값을 13(25/2)로 시작합니다.

 

만약 최솟값 중 가장 큰 값이 13이 되려면 그보다 더 적은 거리가 존재하면 안되겠죠?

 

고로 더 적은 거리를 순차적으로 삭제해줍니다.

 

가장 먼저 2는 1과의 사이가 1이죠? 13보다 적으므로 삭제해줍니다.

 

2를 삭제해줬으므로 현재까지 삭제해준 바위의 갯수는 1개 입니다.

 

 

이제 그 다음 거리는 2를 삭제해줬으므로 10이 됩니다.

 

13보다 적으므로 삭제해줍니다.

 

11을 삭제해줬으므로 삭제해준 바위의 갯수는 2개 입니다.

 

 

 

그 다음은 거리가 13이므로 현재 기준값보다 같기 때문에 삭제해 줄 필요가 없습니다.

 

삭제해주지 않았으므로 다음 바위와 거리는 14부터 재줍니다.

 

 

그 다음은 17이죠? 14와의 거리가 3이므로 13보다 적으므로 삭제해줍니다.

 

삭제해준 바위의 갯수는 3개 입니다.

 

 

그 다음은 21입니다. 14와의 거리가 7이므로 삭제해줍니다.

 

삭제해준 바위의 갯수는 4개 입니다.

 

결과는 아래와 같이 바위가 남고 총 삭제해준 바위의 갯수는 4개 입니다.

 

하지만 삭제해줘야 할 바위의 갯수는 2개죠? 즉, 13은 바위를 삭제해서 만들 수가 없습니다.

 

삭제한 바위가 삭제해줘야 할 바위보다 많으므로 최솟값을 끝 길이를 -1 해주고 반으로 나눠줍니다. (13-1)/2 = 6) 

 

위와 똑같이 진행하면 2,14,21이 삭제되어 총 3개의 바위가 삭제됩니다.

 

아직도 삭제해준 바위의 갯수가 더 많죠?

 

 

 

고로 최솟값을 끝 길이를 -1 해주고 반으로 나눠줍니다. (6-1)/2 = 3

 

2만 삭제되므로 총 삭제되는 바위의 갯수는 1입니다.

 

이젠 삭제해줘야 하는 바위보다 작죠?

 

이럴 땐 시작값을 중간값 +1 해줍니다. (4로 바꿔줍니다.)

 

 

최솟값이 4일 땐 2,14가 삭제되므로 총 삭제되는 바위의 갯수는 2입니다.

 

삭제해줘야 하는 바위와 같으므로 적을 때와 마찬가지로 중간값에 + 1 해줍니다.

최솟값이 5일 땐 2,14,21이 되므로 총 삭제되는 바위의 갯수가 다시 3이 됩니다.

 

 

고로, 최솟값 중 가장 큰 값, 즉 정답은 4가 됩니다.

---

Source Code