프로그래머스 문제 - 외벽 점검

프로그래머스 외벽 점검 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

완전히 동그란 모양의 외벽이 있는 레스토랑이 있습니다.
외벽 중 손상될 수도 있는 외벽들이 존재합니다.
이러한 외벽들을 찾기 위해 정해진 거리를 이동할 수 있는 친구들이 있습니다.
최소한의 친구들을 투입해 모든 취약한 벽을 검사해야 합니다.

문제 풀이

원형이므로 원형 탐색을 사용하여 모든 벽을 최소한의 사람을 사용하여 검색해야 합니다.

최소한의 사람이 필요하기 때문에 외벽 검사를 제일 많이 할 수 있는 사람들부터 시작하여 BFS로 검색해나가며 모든 벽을 검사한 지점을 찾는 방식으로 코드를 작성하였습니다.
하지만 답은 맞지만 두 개의 시간초과가 발생하여 시간을 줄이는 방법을 찾지 못하였습니다.
그래서 다른 방법을 찾아보는데 순열을 이용해 모든 경우의 수를 탐색하여 답을 찾는 방법이 존재하였습니다.

일단 원형탐색을 위해 마지막 지점을 제외한 각 지점별로 (지점 + n)의 지점을 추가해줍니다.
이러면 시계 방향으로 탐색만 해주면서 시계, 반시계 방향 두 개의 모든 탐사를 한번에 할 수 있습니다.

이후 취약한 외벽을 검사할 친구들을 차례대로 벽을 검사하는데 친구들의 위치가 다른 모든 경우의 수, 즉 주어진 배열의 순열을 사용하여 모든 경우의 수를 가지고 외벽을 검사해줍니다.
c++를 사용한다면 next_permutation함수를 사용하여 쉽게 순열을 만들어 낼 수 있습니다.

검사한 값중 제일 작은 값이 답이 됩니다.
모든 검사를 마치더라도 초기화 값을 가진다면 외벽 검사가 불가능한 경우이므로 -1을 return해주면 됩니다.

전체 코드

이번 문제로 순열에 대한 정보를 알 수 있었습니다.

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

int INF = 2100000000;

int solution(int n, vector<int> weak, vector<int> dist) {
    int answer = INF;
    int wallSize = weak.size();
    
    //원형탐색을 위한 값 추가
    for(int i = 0; i < wallSize; i++)
        weak.push_back(weak[i]+n);
    
    sort(dist.begin(), dist.end());
    
    do{
        for(int i = 0; i < wallSize; i++)
        {
            int startWall = weak[i];
            int endWall = weak[i+wallSize-1];
            
            for(int j = 0; j < dist.size(); j++)
            {
                //시작점 지정
                startWall += dist[j];
                
                if(startWall >= endWall)    //시작점과 도착점이 같으면 탐색 종료
                {
                    answer = min(answer, j+1);
                    break;
                }
                
                for(int k = i+1; k < wallSize+i; k++)   //현재 취약 벽을 찾는 친구보다 더 멀리 있는 벽이 나올때까지 검색
                {
                    if(weak[k] > startWall)
                    {
                        startWall = weak[k];
                        break;
                    }
                }
            }
            if(answer == 1)
                return answer;
        }
    } while(next_permutation(dist.begin(), dist.end()));    //모든 친구들의 경우의 수를 검색하기 위해 순열을 찾아 계산해줌
    
    if(answer == INF)
        answer = -1;
    
    return answer;
}

출저

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