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

문제 링크

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

 

 

 

풀이

감이 안잡혀 해설을 보고 풀었다.

시계, 반시계 이동때문에 감이 안잡혔는데 한 방향이 최적이였다.

순환을 직선화 시키는 법과 친구들을 모두 완전탐색(순열)하여 풀었다.

 

// 요약

1) weak[0]+n을 push하고 weak[0]을 erase하여 순환하는 것을 직선화 시켰다.

2) 친구 수를 next_permutation으로 취약 위치가 순환할 때 전부 점검했다.

3) answer가 signed int이므로 -1값을 unsigned int로 비교할 시 최대값이므로 캐스팅하여 비교해주었다.

unsigned int > signed 이므로 unsigned int로 비교하게 됨 + 취약 해결 못할 경우 디폴트로 -1값 리턴

 

++) sort는 문제에서 dist 컨테이너가 오름차순 명시가 없어서 혹시 몰라서 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;
    
    const int weakSize = weak.size();
    sort(dist.begin(), dist.end());     // dist 오름차순 정렬
    
    for(int i=0; i<weakSize; i++){
        // 취약 위치 개수만큼 순환
        do{
            // dist 순서 변경하며 모든 경우
            int w = 0;      // 해결할 weak 인덱스
            int d = 0;        // 해결한 dist 인덱스

            while(d < dist.size()){
                // 친구 수 만큼 반복
                int after = weak[w] + dist[d];        // 1시간 후 위치
                for(; w<weakSize; w++){
                    if(weak[w] > after) break;  // weakSize보다 작으면서 1시간 후 위치보다 클 때까지
                }
                d++;
                if(w == weakSize){
                    // 취약 모두 해결
                    if(d < (unsigned int)answer){
                        answer = d;
                    }
                    break;
                }
            }
        }while(next_permutation(dist.begin(), dist.end()));
        
        weak.push_back(weak[0]+n);      // 마지막 추가
        weak.erase(weak.begin());       // 첫 번째 삭제
    }
    
    return answer;
}