[2020카카오공채] 외벽 점검

https://programmers.co.kr/learn/courses/30/lessons/60062

프로그래머스

으왕.. 다른분들 풀이 참고해가면서 어렵게 푼 문제

순열을 이용해서 푸는 거라고는 생각했지만 순열을 어떻게 구현해야 할지, weak 배열을 어떻게 탐색해야 할지 쉬이 감이 오지 않았다.

 

순열은 algorithm 헤더에 있는 next_permutation을 이용하면 쉽게 구현할 수 있다.

next_permutation에 인자로 배열의 포인터를 넘겨주면 알아서 배열을 다음 순열로 만들어준다.

뿐만 아니라 리턴값으로 bool 값을 반환해주는데, 모든 순열을 다 계산해서 다음으로 계산할 순열이 없다면 false를 반환해준다. 넘나 편한 함수!

 

레스토랑이 원형인 것을 감안해 weak 배열을 2배로 늘려주었다.

2배로 늘려줄 때 뒤에 오는 원소들에 n을 더해서 늘려주면 거리 계산이 용이하다.

 

모든 순열에 대해 weak 배열의 시작점 위치를 바꿔가면서 검사한다.

순열의 원소 순서대로 친구 한명 한명씩 어디까지 검사할 수 있는지를 계산해주어야 하는데

이 부분은 일종의 포인터인 ptr1, ptr2를 사용하였다.

 

#include <string>
#include <vector>
#include <algorithm>

#define MAX_FRIENDS	9

using namespace std;

int solution(int n, vector<int> weak, vector<int> dist) {
	int answer = MAX_FRIENDS;
	int w_size = weak.size();

	// weak 두배로 늘려줌
	for (int i = 0; i < w_size; i++) {
		weak.push_back(weak[i] + n);
	}

	// 모든 가능한 순열에 대해 계산
	while (1) {
		// weak 배열의 시작점 위치 바꿔가며 계산
		for (int i = 0; i < w_size; i++) {
			int ptr1 = i;
			for (int j = 0; j < dist.size(); j++) {
				int ptr2 = ptr1;
				while (ptr2 < i + w_size && weak[ptr2 + 1] - weak[ptr1] <= dist[j]) {
					ptr2++;
				}
				ptr1 = ptr2 + 1;
				// 취약지점을 모두 검사한 경우 break
				if (ptr1 >= i + w_size) {
					answer = min(answer, j + 1);
					break;
				}
			}
		}
		if (!next_permutation(dist.begin(), dist.end())) break;
	}

	if (answer == MAX_FRIENDS) answer = -1;

	return answer;
}