[C++] 백준 2110번 공유기 설치

이분 탐색 문제.

시간 복잡도가 이게 되나? 생각되는 문제지만 이분 탐색 + 되는지 순차적으로 확인 해주면 풀리는 문제이다.

많이 틀렸었는데, 이유는 이분탐색 최소부분을 1부터 시작하지 않고 집의 번호들 중 가장 작은 부분부터 시작해서 틀렸다.

 

문제풀이

이분 탐색을 하면서 나오는 숫자들을 하나씩 가능한지 여부를 살펴보면 된다.

 

이분 탐색은 늘 그렇듯 front < tail일 때까지 고려해주면 된다.

front는 1로 시작해야한다. 처음에 이 부분을 간과해서 집 번호 중 가장 작은 부분부터 시작해서 틀렸다.

만일 집이 3개가 있고 2개의 공유기를 설치한다고 해보자.

집의 번호가 각각 10000, 10001, 10002 이렇게 있다면

가장 멀리 공유기를 설치하는 법은 10000, 10002 이렇게 된다. 따라서 최대 거리는 2이다.

만일 10000부터 고려한다면, 1 ~ 9999는 나올 수가 없으므로 틀린 답이 된다.

 

이분탐색으로 나온 거리가 가능한지 여부는 어떻게 살필 수 있을까? 이 부분은 간단하다.

1. 맨 왼쪽에 있는 집(idx로는 0번째 집)에는 무조건 설치해준다. 여기는 무조건 설치해야 최대 거리가 보장된다.
2. 집을 왼쪽에서(1부터 시작) 탐사하면서 (최근에 공유기를 설치한 집의 좌표 + 거리) <= 현재 탐사중인 집의 좌표 라면 해당 집에 공유기를 설치한다. 아니라면 다음 집으로 넘어간다.
3. 공유기 설치한 집의 개수가 공유기를 설치할 집의 개수와 같다면 가능하다.
4. 모든 집을 고려해도 공유기를 설치할 집의 개수가 안된다면 불가능한 경우이다.

 

시간 복잡도를 고려해보자. k는 집의 개수, n이 최대 집의 번호라고 하자.

1. 이분 탐색을 하기 위해서는 벡터를 정렬해줘야 한다. 정렬하는 데는 O(klog k)의 시간이 걸린다.
2. 이분 탐색의 시간 복잡도는 O(log n)이다.
3. 가능한지 여부를 살피는 데 걸리는 시간은 O(k)가 된다.

k는 최대 200,000 n은 최대 1,000,000,000이고, 위 식은 O(klog k) + O(log n * k) = O(klog n)이 된다.

최악의 경우 200,000 * log(1,000,000,000)인데, log(1,000,000,000)은 대략 30 정도이다.

따라서 최악의 경우 6,000,000 정도의 연산이므로 문제의 시간제한 내에 풀 수 있다.

 

코드를 살펴보자.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int houseCnt, shareCnt;
vector<int> houseVec;
int ans;

사용한 STL과 변수

 

벡터를 사용하기 위한 vector STL, sort 메서드를 사용하기 위해 algorithm STL을 include했다.

• houseCnt, shareCnt : 입력받는 N과 C이다.
• houseVec : 입력받는 집의 번호를 저장하는 벡터이다.
• ans : 출력하는 값이다. 최대로 큰 할당 가능한 거리를 출력한다.

 

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> houseCnt >> shareCnt;
	
	int input;
	for (int i = 1; i <= houseCnt; i++) {
		cin >> input;
		houseVec.push_back(input);
	}

	sort(houseVec.begin(), houseVec.end());

	int front = 1; // 틀린 이유. 제일 작은 걸 제일 작은 집의 번호로 시작해서 틀림. 무조건 1부터 탐색해야 함.
	int tail = houseVec[houseVec.size() - 1];
	int middle = 0;

	while (front < tail) {
		middle = (front + tail) / 2;

		bool check = checkAllocate(middle);

		if (check) {
			front = middle + 1;
			ans = middle;
		}
		else {
			tail = middle;
		}
	}

	cout << ans;

	return 0;
}

메인함수

 

처음에 N과 C를 입력받고, 집의 번호를 입력받은 후에 벡터를 sort() 메서드로 정렬해준다.

 

그리고 이분 탐색을 시작한다.

front를 1로 설정해줄 수 있었다면 쉽게 맞출 수 있을 것이다.

tail은 집의 번호들 중 가장 큰 값으로 설정해준다.

그리고 checkAllocate() 메서드로 이분 탐색으로 탐색한 값이 할당 가능한 값인지 체크한다.

만일 할당 가능한 값이라면 ans에 middle을 저장해두고, front를 middle + 1로 높여준다.

할당 불가능한 값이라면 tail을 middle로 낮춰준다.

 

처음에 할당 가능한 값이라면 front를 middle로 바꾸고, 불가능하면 tail을 middle - 1로 할당하도록 만들었었는데,

이는 TC가 무한루프를 돌게 만들었다.

이분탐색에서는 front를 크게 해주고, tail은 middle로 만들어줘야 하는데, 반대로 생각했다.

 

bool checkAllocate(int size) {
	int lastAllocate = houseVec[0];
	int curAllocateCnt = 1;

	for (int i = 1; i < houseVec.size(); i++) {
		int curHousePoint = houseVec[i];
		int diff = curHousePoint - lastAllocate;
		if (diff >= size) {
			lastAllocate = curHousePoint;
			curAllocateCnt++;
		}

		if (curAllocateCnt == shareCnt) {
			return true;
		}
	}

	return false;
}

이분 탐색으로 찾은 middle 값이 할당 가능한지 여부를 살펴보는 메서드

 

• lastAllocate : 마지막으로 할당한 집의 좌표
• curAllocateCnt : 현재 공유기를 할당한 집의 개수
• curHousePoint : 현재 탐사하는 집의 좌표
• diff : 마지막으로 할당한 집의 좌표와 현재 탐사하는 집의 좌표의 차이
• size : 이분 탐색으로 검사할 middle 값

 

메서드는 다음과 같은 로직으로 작동한다.

1. 제일 왼쪽 집(0번 idx)에 우선 집을 할당한 후에 1번 idx부터 집 탐사를 시작한다.
2. 현재 집의 좌표 - 마지막으로 할당한 집의 좌표 >= middle 이라면 현재 집에 공유기를 할당한 후에 lastAllocate, curAllocateCnt 변수를 갱신한다.
3. 만일 현재 할당한 집의 개수가 할당해야할 공유기의 개수와 같다면 true를 return한다. 아니라면 계속 탐사한다.
4. 모든 집을 탐사했는데 할당한 집의 개수가 모자라다면 false를 return한다.

 

최근에 학교 수업에서 아예 똑같은 문제가 나왔었다.

(내가 듣는 건 아닌데, 주변 사람들이 보내줬다.)

이분탐색 문제를 안 푼지 너무 오래돼서 금세 가물가물해졌다.

요즘 너무 삼성 구현 문제들만 푼 것 같다...

다시 알고리즘 문제들도 겸비해서 풀어야겠다.

 

GitHub - kimyunseok/cpp: my study-record

코드 전문은 위에서 확인이 가능하다.