[문제풀이] 징검다리

업데이트:

문제 링크 : 징검다리

풀이 시간 : 30분

1. 문제 풀이

n개의 바위를 제거하여 바위 사이의 거리 중 가장 짧은 거리 중 최대 거리를 찾는 문제

바위의 수가 50000개 이하여서 완전 탐색으로는 안된다고 판단

이진 탐색으로 가장 짧은 거리 중 최대 거리를 설정하여 가능 여부를 확인

1) 바위들의 위치 정렬

2) 이진 탐색으로 mid 값 결정

3) 전 바위와의 거리를 이용하여 mid와 비교

3-1) mid이 클 경우, mid가 최소가 아니므로 현재 바위 제거 후 전 바위 유지

3-2) 작을 경우, 전 바위 위치를 현재 바위로 변경

4) mid의 가능 여부 확인

4-1) 제거한 바위 수가 n보다 작거나 같을 경우, start = mid

4-2) 클 경우, end = mid-1

2. 소스 코드

    public int solution(int distance, int[] rocks, int n) {
		// 바위들의 위치 정렬(오름차순)
		Arrays.sort(rocks);
		int[] arr = new int[rocks.length + 2];
		// 시작 바위
		arr[0] = 0;
		for (int i = 0; i < rocks.length; i++) {
			arr[i + 1] = rocks[i];
		}
		// 끝 바위
		arr[rocks.length + 1] = distance;
		int start = 1;
		int end = distance;
		int mid;
		// 바위 사이의 거리의 최소값 중 가장 큰 값 찾기
		// 이진 탐색으로 검색
		while (start < end) {
			// mid 값으로 가능한 거리인지 판단
			mid = (start + end) / 2+1;
			int prev = 0;
			// 바위 제거 횟수
			int count = 0;
			boolean check = true;
			for (int i = 1; i < arr.length; i++) {
				// 현재 바위와 전 바위의 거리
				int temp = arr[i] - prev;
				// mid 값보다 작으면 mid 값이 최소가 아니므로 제거
				if (mid > temp) {
					count++;
					// 제거된 바위가 제거 할 수 있는 수보다 크면 종료
					if (count > n) {
						check = false;
						break;
					}
				} else {
					// 전 바위 변경
					prev = arr[i];
				}
			}
			if (check) {
				start = mid;
			} else {
				end = mid - 1;
			}
		}
		return start;
	}

3. 후기

Level 4 문제치고는 쉬운 문제였다.

문제 옆에 이분 탐색이라는 말이 써있기 때문에 빨리 해결하였다.

상반기 코딩 테스트에서 이분 탐색을 사용하는 문제가 종종 보였던거 같은데 연습으로 풀기 좋은 문제였다.

참고