[틀림] 프로그래머스 외벽점검 // 원형배열, 순열

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

프로그래머스

* 풀이

• n이 작음 (15) -> 비트마스킹? -> 내부에서 순서도 중요하네? -> 그냥 순열?
• idx가 사람의수이면서 && dist의 index 역할
• j는 weakArr(weak를 시작점에따라 바꾼것) 의 index임
• dist를 앞부터 weakArr에 집어 넣어보는 완전탐색 방법.

• 원형배열 구현 , 거리가 중요한경우
  • 결론 : startIdx기준으로 뒤넣고, 앞넣을때 배열 size만큼 더해주면된다.

vector<int> make(int startIdx, vector<int>& weak){
    vector<int> ret;
    if(startIdx==0) return weak; //0부터시작은 그냥 자기자신임
    
    for(int i=startIdx;i<weak.size();++i){ // [1 5 6 7] 에서 [5 6 7] 넣기
        ret.push_back(weak[i]);
    }
    for(int i=0; i<startIdx;++i){ // 앞에 남은것들 , 1을 1+12해서 넣기
        ret.push_back(weak[i]+N);
    }
    return ret;
}

• 시간복잡도
  • weak(15) * weak(15) * dist 순열 8! < 1억 -> 가능

#include <bits/stdc++.h>

using namespace std;

int ret=987654321;
int N;

int fac(int n){
    if(n==1) return 1;
    return n * fac(n-1);
}

vector<int> make(int startIdx, vector<int>& weak){
    vector<int> ret;
    if(startIdx==0) return weak; //0부터시작은 그냥 자기자신임
    
    for(int i=startIdx;i<weak.size();++i){ // [1 5 6 7] 에서 [5 6 7] 넣기
        ret.push_back(weak[i]);
    }
    for(int i=0; i<startIdx;++i){ // 앞에 남은것들 , 1을 1+12해서 넣기
        ret.push_back(weak[i]+N);
    }
    return ret;
}

void testmake(){
    vector<int> vv = {1,5,6,7};
    vector<int> tmp = make(1,vv);
    for(auto i :tmp){
        cout<<i<<" ";
    }
}

int solution(int n, vector<int> weak, vector<int> dist) {

    N=n;
    // cout<<fac(8);
    sort(dist.begin(),dist.end()); // 순열위해 정렬필요
    // int n = weak.size();
    
    do{
        for(int i=0;i<weak.size();++i){ //weak를 순열돌리기 (시작위치 다르게)
            vector<int> weakArr = make(i,weak);
            int idx=0; //dist의 idx == 사람수
            // int i=0; // weak의 idx
            int cur = weakArr[0] + dist[0]; //현재사람의 커버가능한 최대거리
            int flag=1; //가능한지
            for(int j=0;j<weakArr.size();++j){ // j : weak의 idx
                if(weakArr[j] > cur){ //커버할수없는경우, 새사람필요
                    if(idx + 1 == dist.size()){ //새사람이 필요한데, 사람이없으면 실패
                        flag = 0; break;
                    }
                    cur = weakArr[j] + dist[++idx];
                }                
            }
            if(flag) ret = min(ret, idx+1); //인덱스+1 == 사람수
        }
    }while(next_permutation(dist.begin(),dist.end()));
    
    // testmake();
    if(ret==987654321) return -1;
    return ret;
}