[2020 KAKAO BLIND RECRUITMENT][C++] 외벽점검

문제 바로가기

코딩테스트 연습 - 외벽 점검

 

<문제 풀이 Logic>

1. 각 외벽 사이의 공간 길이를 empty 벡터에 넣는다. (이 벡터의 길이는 weak.size() +1 )
2. dist 벡터를 내림차순으로 sort 한다. 많은 공간을 탐색할 수 있는 친구부터 탐색하면 탐색횟수를 줄일 수 있다. 
3. dist의 순열을 구한다. -> 순서가 달라지면 다른 경우이기 때문에
4. 각 순열(set)의 경우에 모든 외벽(tmp_empty)을 탐색할 수 있는 지 검사한다. 외벽은 원형으로 이루어져 있기 때문에 rotate 해주어야 한다. 현재 보는 tmp_empty + prev가 현재 보는 set보다 작거나 같으면 tmp_empty의 idx를 증가시킨다. 현재의 tmp_empty는 prev에 더해주어 현재 set이 얼만큼의 외벽을 점검할 수 있는지 알 수 있도록 한다. prev + 현재 tmp_empty가 현재 보는 set보다 크면 그 set은 더 이상 외벽 점검을 할 수 없다는 뜻이므로 tmp_empty, set의 idx 모두 증가시키고 prev는 0으로 초기화 시킨다. 이 때 tmp_empty의 idx를 증가시키는 이유는 내가 tmp_empty에 저장해둔 값들은 각 외벽의 사이 거리기 때문이다. 
5. 모든 외벽을 탐색한 경우를 찾는다면 함수에서 빠져나와 그 때의 set.size()값을 return 해주면 된다. 외벽점검 인원의 최소를 출력해야하지만, 이때 min값을 찾을 필요가 없다. 왜냐하면 순열을 만들 때 size를 오름차순으로 키워가면서 만들기 때문이다. 

 

-전체 코드-

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <string.h>

using namespace std;

int visited[8];
vector<int> set;
bool flag = false;

vector<int> rotate(vector<int> arr)
{
	vector<int> tmp;
	for (int i = 1; i < arr.size(); i++) {
		tmp.push_back(arr[i]);
	}
	tmp.push_back(arr[0]);

	return tmp;
}

void Permutation(int now_c, int goal_c, vector<int> empty, vector<int> dist)
{
	if (now_c == goal_c)
	{
		/*cout << "순열" << endl;
		for (int i = 0; i < set.size(); i++)
			cout << set[i] << " ";
		cout << endl << endl;*/

		vector<int> tmp_empty = empty;
		//순열 완성
		for (int k = 0; k < tmp_empty.size(); k++)
		{
			/*for (int t_c = 0; t_c < tmp_empty.size(); t_c++)
				cout << tmp_empty[t_c] << " ";
			cout << endl;*/

			int j = 0, i = 0, prev = 0;
			flag = false;
			while (1)
			{
				if (i >= tmp_empty.size())
				{
					flag = true;
					break;
				}

				if (j >= set.size())
				{
					flag = false;
					break;
				}

				if (tmp_empty[i] + prev <= set[j])
				{
					prev += tmp_empty[i];
					i++;
				}
				else {
					prev = 0;
					j++;
					i++;
				}
			}

			if (flag == true) {
				cout << set.size() << endl;*/
				
				return;
			}

			tmp_empty = rotate(tmp_empty);
		}
		
		return;
		
	}

	for (int i = 0; i < dist.size(); i++)
	{
		if (!visited[i]) {
			set.push_back(dist[i]);
			visited[i] = 1;
			Permutation(now_c + 1, goal_c, empty, dist);

			if (flag == true)
				return;

			set.pop_back();
			visited[i] = 0;

			
		}
	}
}

bool desc(int a, int b)
{
	return a > b;
}
int solution(int n, vector<int> weak, vector<int> dist) {
	vector<int> empty;
	
	sort(dist.begin(), dist.end(), desc);

	for (int i = 1; i < weak.size(); i++)
	{
		empty.push_back(weak[i] - weak[i - 1]);

	}
	empty.push_back((weak[0] + n) - weak[weak.size()-1]);

	/*for (int i = 0; i < empty.size(); i++)
	{
		cout << empty[i] << " ";
	}
	cout << endl;*/


	for (int c = 1; c <= dist.size(); c++)
	{
		set.clear();
		memset(visited, 0, sizeof(visited));
		Permutation(0, c, empty, dist);
		if (flag == true)
		{
			cout << set.size() << endl;
			return set.size();
		}

	}
	/*if (dist.size() == weak.size())
	{
		cout << dist.size() << endl;
		return dist.size();
	}*/

	return -1;
}

int main()
{
	int n;
	vector<int> weak;
	vector<int> dist;

	n = 12;
	weak = { 1, 5, 6, 10 };
	dist = { 1, 2, 3, 4 };

	solution(n, weak, dist);//결과: 2

	n = 12;
	weak = { 1, 3, 4, 9, 10 };
	dist = { 3, 5, 7 };

	solution(n, weak, dist);//결과: 1

	n = 200;
	weak = { 0, 100 };
	dist = { 1, 1 };

	solution(n, weak, dist);//결과: 2

	n = 12;
	weak = { 0, 10 };
	dist = { 1, 2 };

	solution(n, weak, dist);//결과: 1

	n = 50;
	weak = { 1 };
	dist = { 6 };

	solution(n, weak, dist);//결과: 1

	n = 30;
	weak = { 0, 3, 11, 21 };
	dist = { 10,4 };

	solution(n, weak, dist); //결과: 2
	return 0;
}