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

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;
}

 

 

* 25.8.22. 2회독

순열, 조합 -> 복잡쓰

Weak 배열의 뒤쪽을 +n칸 으로 채움 => 계산 easy, 원형배열 행동영역

구멍배열을 index 기준으로 1칸씩 메꿔보면 됨.

그리디 : 거리가 큰 사람부터 사용하는게 최적해 이다.

상태 : (사용한사람수, 시작위치, 방문비트)

작동예시

import java.util.*;

class Solution {
    
    static int N,len,ret=Integer.MAX_VALUE;
    static int[] Weak;
    static Integer[] Dist;
    static int[][] arr;
    
    void go(int cnt, int pos, int vis) {
        
        // 사람을 다 써버린 경우 (가지치기)
        if(cnt >= Dist.length) {
            return;
        }
        
        // 현재 사람이 커버할 수 있는 범위 계산
        int coverage = Dist[cnt];
        
        // pos부터 시계방향으로 coverage만큼 이동하며 구멍들을 메움
        for(int i = 0; i < len; ++i) {
            int currentPos = (pos + i) % len;
            
            // 거리 계산 (원형이므로 조심)
            int distance;
            distance = Weak[pos + i] - Weak[pos];
            
            if(distance > coverage) {
                break;
            }
            
            vis |= (1 << currentPos);
        }
        
        // 모든 구멍을 메운 경우
        if(vis == (1 << len) - 1) {
            ret = Math.min(ret, cnt + 1);
            return;
        }
        
        // 아직 메우지 못한 구멍에서 다음 사람 투입
        for(int i = 0; i < len; ++i) {
            if((vis & (1 << i)) == 0) { // 아직 메우지 못한 구멍
                go(cnt + 1, i, vis);
            }
        }
    }
    
    public int solution(int n, int[] weak, int[] dist) {
        
        arr = new int[n][n];
        // System.out.println(Arrays.deepToString(arr));
        len=weak.length;
        N = n;
        Weak = new int[len*2];
        // 배열붙이기 +n 시간
        for(int i=0;i<len;++i){
            Weak[i]=weak[i];
        }
        for(int i=len;i<2*len;++i){
            Weak[i]=weak[i-len]+n;
        }
        
        // 그리디 : 반경이 높은것부터 투입하는게 최적해이다.
        Dist = Arrays.stream(dist).boxed().toArray(Integer[]::new);
        Arrays.sort(Dist, (a,b)->b-a); // int[]는 람다식 안됨
//         System.out.println(Arrays.toString(Dist));
//         System.out.println(Arrays.toString(Weak));
        
        for(int i=0;i<weak.length;++i){
            go(0,i,0);
        }
        
        if(ret==Integer.MAX_VALUE) return -1;
        
        return ret;
    }
}