[C++ 알고리즘] 44. 마구간 정하기

 


44. 마구간 정하기

인프런의 it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 수강하여 공부한 내용을 기록한 포스트입니다. 문제는 공개하지 않습니다.


풀이과정

43번 문제와 마찬가지로 이분검색 문제이다. 이분검색 문제에서는 이분검색할 범위를 찾는 것이 중요한 것 같다.

  1. 이분검색할 최대 범위를 찾는다. 이 범위는 배열의 크기가 아니므로 프로그래머가 찾아야한다.
  2. 그 값이 조건에 타당한지 검사 후 계속 이분검색을 수행하여 답을 찾는다.
    이 문제는 이분검색할 범위를 입력의 최대값으로 정해야 해서 먼저 sort()를 통해 오름차순으로 정렬해주었다. 1~(입력의최댓값)이라는 범위를 찾고 나니 값을 결정하는 것은 쉬웠다.


코드

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	int n, m;
	scanf("%d %d", &n, &m);

	vector<int> arr(n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
	}
	sort(arr.begin(), arr.end());

	int left = 1, right = arr[n - 1] - arr[0], mid;
	int cnt, res = 0, pre = 0;

	while (left <= right) {
		mid = (left + right) / 2;

		cnt = 1;
		pre = 0;

		for (int i = 1; i < n; i++) {
			if (arr[i] - arr[pre] >= mid) {
				cnt++;
				pre = i;
			}
		}

		if (cnt >= m) {
			res = mid;
			left = mid + 1;
		}
		else {
			right = mid - 1;
		}
	}

	printf("%d", res);

	return 0;
}


:bookmark: REFERENCE
인프런 it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비