(C++) - 프로그래머스(2020 KAKAO BLIND RECRUITMENT) : 외벽 점검

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

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

brute force로 푼 문제였습니다.

 

풀이방법

 1. dist를 오름차순으로 정렬해줍니다.

 2. 조합을 통해 dist를 정해줍니다. dist배열의 왼쪽이 투입할 우선순위가 제일 높습니다. 매 조합으로 dist를 정할 때마다 weak를 계속해서 돌리며 최소의 투입인원을 찾습니다. 8! * 15 * 8 = 4838400으로 1초 내에 수행 가능합니다. weak를 돌릴 때 1부터 시작해 돌려 마지막에 weak[0] + n을 넣어줍니다. weak[0]번째 와 weak[size()-1]사이의 거리는 시계방향또는 반시계방향으로 출발방향에 따라 거리가 달라질 수 있기 때문에 n을 더해줘 차이를 줄일 수 있습니다.

 

   2-1. dist.size()까지 loop를 돌며 다음을 수행합니다. 취약지점 weak[weakIdx]부터 dist[distIdx] 까지가 distIdx번 인원을 투입했을 때 점검할 수 있는 길이입니다. 따라서 coverLength = weak[weakIdx] + dist[distIdx]가 되며 이것이weak[weakIdx] 이상인 동안 weakIdx를 1씩더해줍니다. 만약 모두 coverLength보다 작아 모든 취약지점 점검을 완료했다면 break;해줍니다. 

 

   2-2. loop를 나와 모든 취약점검이 가능하다면 distIdx + 1이 투입인원이므로 answer와 비교해 작은 값을 answer에 저장합니다.

 

 3. 모든 방법에 투입해도 점검할 수 없다면 -1을 아니면 최소의 투입 인원 값인 answer를 반환해줍니다.

 

Code

#include <bits/stdc++.h>
using namespace std;

vector <int> rotateWeak(int n, vector<int> weak){
    vector <int> tmp;
    for(int i = 1; i < weak.size(); i++) tmp.push_back(weak[i]);
    tmp.push_back(weak[0] + n);
    return tmp;
}

int solution(int n, vector<int> weak, vector<int> dist) {
 
    int answer = 0x3f3f3f3f;
 
    sort(dist.begin(), dist.end());
    do {
        for (int i = 0; i < weak.size(); i++) {
            weak = rotateWeak(n,weak);
 
            int weakIdx = 0;
            int distIdx = 0;

            for (distIdx = 0; distIdx < dist.size(); distIdx++) {
                int coverLength = weak[weakIdx] + dist[distIdx];
                while (weakIdx != weak.size() && coverLength >= weak[weakIdx]) weakIdx++;
                if(weakIdx == weak.size()) break;
            }
            if (weakIdx == weak.size()) answer = min(answer,distIdx + 1);
        }
    } while (next_permutation(dist.begin(), dist.end()));
    if(answer == 0x3f3f3f3f) return -1;
    return answer;
}