섹션 6. Sorting and Searching(정렬, 이분검색과 결정알고리즘) 10. 마구간 정하기(결정알고리즘)

문제

• N개의 마구간이 수직선상에 있습니다. 각 마구간은 x1, x2, x3, ......, xN의 좌표를 가지며, 마구간간에 좌표가 중복되는 일은 없습니다.
• 현수는 C마리의 말을 가지고 있는데, 이 말들은 서로 가까이 있는 것을 좋아하지 않습니다. 
• 각 마구간에는 한 마리의 말만 넣을 수 있고, 가장 가까운 두 말의 거리가 최대가 되게 말을 마구간에 배치하고 싶습니다.
• C마리의 말을 N개의 마구간에 배치했을 때 가장 가까운 두 말의 거리가 최대가 되는 그 최대값을 출력하는 프로그램을 작성하세요.

입력

• 첫 줄에 자연수 N(3<=N<=200,000)과 C(2<=C<=N)이 공백을 사이에 두고 주어집니다.
• 둘째 줄에 마구간의 좌표 xi(0<=xi<=1,000,000,000)가 차례로 주어집니다.

출력

• 첫 줄에 가장 가까운 두 말의 최대 거리를 출력하세요.

입출력 예제

---

풀이방식

이번 문제는 이분검색를(을) 사용하여 푸는 문제이다.

---

이분검색이란 정렬된 데이터를 가지고 자료를 반으로 나누어 검색하는 방식이다.

찾고 싶은 데이터(키 값), 시작 위치에 대한 값, 종료 위치에 대한 값, 중간 위치에 대한 값이 필요하다.

중간 위치의 값을 키 값과 비교하여 같다면 검색 종료, 작다면 왼쪽 데이터를 다시 검사하고 크다면 오른쪽 데이터를 다시 검사한다.

---

설계과정

1. 말 사이 거리의 중간값을 찾는다.

2. 중간값의 간격으로 총 몇 마리가 나오는지 구한다.

3. 더 좋은 결과를 얻기 위해 탐색 범위를 좁혀가며 결과를 구한다.

4. 탐색 범위가 끝날 때까지 반복한다.

---

풀이과정

1. 값들을 입력받는 코드를 작성한다.

 

2. 결과를 출력할 solution 메소드와 말의 마리수 출력할 count 메소드를 선언한다.

 

3. solution 메소드부터 작성해보자.

 

4. 결과값을 저장할 result 변수를 선언하고, 0으로 초기화한다.

 

5. 배열을 오름차순으로 정렬한다.

• Arrays.sort() : 배열을 자동으로 오름차순으로 정렬해준다.

6. lt와 rt를 선언하고 값을 할당한다.

• lt : 범위의 시작으로, 무조건 1부터 시작한다. (말 사이의 거리는 최소 1부터 시작한다.)
• rt : 범위의 끝으로, arr 배열의 맨 마지막 좌표 값이다. 

7. lt 가 rt보다 작거나 같을 때 도는 while 문을 작성한다.

• 탐색하는 범위가 배열을 초과하면 멈추도록 한다.

8. lt와 rt를 더한 후에 2로 나눠서 중간값인 mid를 정한다.

• 이분검색을 사용하기 위한 중간값을 설정한다.

9. count() 메소드를 사용해서 C과 비교하며 탐색 범위를 줄인다.

 

10. 위 과정을 위해 count() 메소드를 작성해보자.

 

11. 각 변수를 선언하고 초기화한다.

• cnt : 배치한 말의 수를 의미한다.
• ep : 가장 왼쪽 좌표를 의미한다.
• dist : 말 사이의 거리로, mid 값이 들어온다.

12. arr[ i ] - ep 가 dist보다 크거나 같으면 cnt를 추가하고 ep에 arr[ i ] 값을 넣는다.

• arr 배열에 i번째 값에서 ep 값을 빼는 것은 두 말 사이의 거리를 구하는 것이다.
• 두 말 사이의 거리가 dist보다 크거나 같으면 말을 한 마리 더 배치할 수 있으므로 cnt를 추가한다.
• 그리고 ep에 arr[ i ] 값을 넣어서 다음 범위를 탐색한다.
• 해당 과정을 배열의 길이만큼 반복하며 결과를  찾는다.

13. 작성한 count() 메소드를 사용한 결과가 C보다 작거나 같다면 결과값에 추가하고, lt에 1을 더한다.

• count로 리턴된 마리수가 C 보다 크거나 같으면 mid 값이 정답으로 유효한 후보이다.
• 거리가 최대인 값을 구해야하므로 mid보다 큰 값으로 유효한 값이 더 나오는지 찾기 위해 lt + 1 을 한다.

14. C보다 큰 경우에는  rt에 1을 빼서 재탐색한다.

• 해당 거리로는 모든 말을 배치할 수 없으므로 mid 값을 줄여서 다시 탐색한다.

15. 위 과정을 탐색 범위가 끝날때까지 반복한다.

---

해당 글은 인프런 > 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비(김태원)강의를 참고하여 작성하였습니다.