[프로그래머스] 외벽 점검

풀이)

모든 경우를 다 확인해주면 되는 문제이다.

풀이과정은 이러하다.

1. 원형탐색이여서, 주어진 weak배열을 두배로 늘린 배열을 하나 선언해준다.

   거리계산을 원할하게 하기 위해서인데,

   만일 weak = {1,5,6,10} , n =12이면 

          two_weak = {1,5,6,10,1+12,5+12,6+12,10+12} = {1,5,6,10,13,17,18,22} 이런식으로 저장해준다.

   그러면, 10에서부터 출발해도 거리 계산하기 쉽다.

   10 -> 1 : 10 -> 13까지니깐 거리 3

   10 -> 5 : 10 -> 17까지니깐 거리 7

   ** 시계방향만 고려한다. 모든 취약 지점에서의 경우를 다 봐줄 것이기에 반시계 방향은 생각해줄 필요 없다.

2. 각 취약 지점위치에서 친구들이 출발한다고 생각해, 각 위치마다 for문을 돌려준다.

      for문 내부

{

 친구들을 내보내는 순서를 순열로 정해서, 그 위치에서부터 정해진 순서대로 친구들을 내보낸다.

 모든 weak를 돌았다면 answer을 바꿔준다.

}

순열은 algorithm header의 next_permutation()함수를 사용해줬다.

코드)

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

int solution(int n, vector<int> weak, vector<int> dist) {
    int answer = -1;
   vector <int> two_weak(weak);
    for(int i=0;i<weak.size();i++){
        two_weak.push_back(weak[i] + n);
    }

    sort(dist.begin(),dist.end()); //친구들의 순서 정렬
    for(int i=0;i<weak.size();i++){
        //cout << "*****************시작 위치: " << weak[i] << endl;
        do{
            int w = i; //w : 취약 지점 인덱스
            int d = 0;  // d : 친구 인덱스
            int cnt =0;
            //친구들이 갈 수 있는 취약 지점 탐색
            for (d = 0; d < dist.size(); d++) {
                int fin = two_weak[w] + dist[d];
                while (fin >= two_weak[w]) {
                    w++; 
                    cnt++;
                    if (cnt == weak.size()) { 
                        break;
                    }
                }
                if (cnt == weak.size()) {
                    break;
                }
            }

            //모든 지점이 다 탐색되었을 경우 -> answer update
            if (cnt == weak.size()) {

                if (answer == -1 ) {
                    answer = d+1;
                }
 else answer = min(answer,d+1);

            }


        }while(next_permutation(dist.begin(),dist.end()));
    }


    return answer;
}