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

이 문제는 원형 탐색, 순열을 이용한 완전 탐색을 이용해서 문제를 풀었다.

 

이 문제에서 핵심은 시계, 반시계 방향으로 두 가지 탐색을 하는 것이 아닌, 시계 방향 하나로만 탐색해도 전체 가짓수를 셀수 있다는 것이다.

또한 dist가 큰 사람부터 사용하는 것이 더 적게 지우는데 유리하다는 것이다.

 

이 두가지를 이용해서 문제를 풀었으나, 13번 테스트 케이스만 시간 초과가 났다. 검색을 통해 순열을 이용해서 부분 배열에 대한 순서쌍을 모두 탐색하는 방식으로 문제를 푸는 것을 확인했다.

 

내가 이전에 풀었던 방식으로는 아마 중복된 경우를 같이 카운트해서 시간 초과가 났을 확률이 높다고 생각했다. Java에는 순열 표준 라이브러리가 없어서 아쉬웠다. 그래서 C++로 풀었다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int N;

vector<int> subArray(vector<int> weak, int begin, int end) 
{
    vector<int> result;
    
    for (int i = begin; i < end; i++) 
    {
        result.push_back(weak[i]);
    }
    
    return result;
}

vector<int> clock(vector<int> weak, int dist) 
{
    int start = weak.front();
    int end = start + dist;
    
    vector<int> result;
    
    for (int w : weak) 
    {
        if (w <= end)
        {
            continue;
        }
        result.push_back(w);
    }
    
    return result;
}

bool check(vector<int> weak, vector<int> subArr, int index) 
{
    if (index == subArr.size()) 
    {
        return false;
    }
    
    int present = subArr[index];
        
    if (present >= N - 1) 
    {
        return true;
    }
        
    vector<int> clockResult = clock(weak, present);
        
    if (clockResult.empty()) 
    {
        return true;
    }
        
    if (check(clockResult, subArr, index + 1)) 
    {
        return true;
    }
    
    return false;
}

int solution(int n, vector<int> weak, vector<int> dist) 
{
    N = n;
    
    reverse(dist.begin(), dist.end());
    
    for (int people = 1; people <= dist.size(); people++) 
    {
        vector<int> subArr = subArray(dist, 0, people);
        
        for (int start = 0; start < weak.size(); start++)
        {
            vector<int> weaks;
            
            for (int i = start; i < weak.size(); i++)
            {
                weaks.push_back(weak[i]);
            }
            
            for (int i = 0; i < start; i++)
            {
                weaks.push_back(weak[i] + N);
            }
            
            do
            {
                if (check(weaks, subArr, 0))
                {
                    return people;
                }
            } while(next_permutation(subArr.begin(), subArr.end()));   
        }
    }
    
    return -1;
}