[ 프로그래머스 외벽 점검 (Lv3) ] (C++)

프로그래머스의 외벽점검(Lv3) 문제이다.

[ 문제풀이 ]

문제의 난이도가 난이도인지라 천천히 하나씩 접근해보자.

지금부터는 본인이 진행했던 과정과, 그 과정에 대한 구체적인 설명을 나열하는 식으로 진행하겠다.

또한, 코드가 조금 길고 복잡해질 수 있어서 중간중간 코드에 대한 부연설명까지 첨가하면서 문제를 해결해보자.

#1 : 주어지는 매개변수 'dist'에 대한 내림차순 정렬

먼저, 주어지는 입력을 보면, weak매개변수, 즉, 취약지점에 대한 정보는 "오름차순으로 정렬된 상태"로 주어지지만,

dist매개변수, 즉, 취약지점을 점검할 수 있는 친구들이 움직일 수 있는 거리는 오름차순으로 정렬된 상태로 주어진다는

말이 없다. 즉 ! 순서가 뒤죽박죽으로 주어질 수 있다는 것을 의미한다.

그런데 직관적으로 생각해 봤을 때, "움직일 수 있는 거리가 가장 긴 친구들부터 투입" 하는 것이 유리할 것이다.

왜냐하면, 움직일 수 있는 거리가 짧은 친구들 여러명에서 점검해야 하는 과정을, 거리가 긴 친구들 한명에서 점검할 수 있는 가능성이 있기 때문이다.

정리해보면, "움직일 수 있는 거리가 긴 친구가 한 번에 하지 못하는 거리를, 상대적으로 움직일 수 있는 거리가 짧은 친구가 한번에 할 수 있는 경우"는 존재하지 않는다. 직관적으로 봤을 때 당연한 이야기이다.

그래서 가장 먼저 본인은 주어진 매개변수 dist를 내림차순으로 정렬을 시켜 주었다.

순서대로 뽑아갈 때, 거리가 가장 긴 친구들부터 무조건 뽑을 수 있도록 설정해 준 것이다.

#2 : 탐색을 해보지 않아도, 정답 도출이 가능한 경우 처리.

탐색을 해보지 않아도 정답을 알 수 있는 경우가 있다.

극단적인 예를 한번 들어보면 다음과 같은 경우이다.

취약지점(weak) : [ 1 , 3 ] , 움직일 수 있는 거리(dist) : [ 1 , 10 ]

이렇게 주어진 경우를 살펴보자. 그림으로 나타내면 다음과 같은 경우이다.

.

위와 같이, 취약지점이 저렇게 2개의 지점이 존재할 때, 움직일 수 있는 거리가 1과 10인 친구가 있는 것이다.

먼저 거리가 1인 친구는 딱 봐도 한번에 해결을 할 수가 없다. 하지만 10인 친구는 딱 봐도 한번에 해결을 할 수가 있다.

그런데 우리는 #1번 과정에서, dist를 내림차순으로 정렬하였기 때문에, [ 10 , 1 ] 로 설정이 되어 있을 것이다.

즉 ! "가장 많이 움직일 수 있는 친구의 움직일 수 있는 거리가 취약지점의 시작점과 끝점간의 거리보다 더 큰 경우" 에는 바로 1을 return 해버리면 되는 것이다.

위의 그림에서 취약지점의 시작점은 '1'이고 끝점은 '3'이다. 이 2개의 지점 간의 차이는 2가 되고, 가장 많이 움직일 수 있는 친구가 움직일 수 있는 거리는 10이기 때문에, 2 <= 10 이기 떄문에 ! 계산을 해보지 않아도 바로 1명만 투입하면 된다는 것을

알 수 있다는 것이다.

그런데 ! 문제가 하나 있다. 취약 지점에서 어디가 시작점이고 어디가 끝점일까? 주어지는 입력이 원형형태로 주어지기 때문에, 시작점과 끝점을 설정하기가 어렵다. 따라서 모든 경우를 다 해보는 것이다.

예제입력2가 이 Case에 해당하는 입력인데, 한번 같이 살펴보자. 예제입력2에 대한 그림을 가져오면 다음과 같다.

.

예제입력2의 취약점들을 나타낸 것이고, 점검하는 친구들이 움직이는 거리를 내림차순으로 정렬해서 적어보면

[ 7 , 5 , 3 ] 이 된다. 그럼 가장 많이 움직일 수 있는 친구의 움직일 수 있는 거리 = 7 이다.

그런데 위의 그림에서 간단하게 생각해서, "숫자가 가장 지점을 시작점, 숫자가 가장 큰 지점을 마지막점"으로 설정을 한다면, 시작점은 '1', 끝점은 '10'이 된다. 이 둘의 거리는 9가 되고, 7만큼 움직일 수 있는 친구 혼자서는 해결하지 못하는 것으로 판단된다. 하지만 ! 여기서 끝내지 말고, "모든 점을 시작점으로 설정" 하는 과정을 반복해보자.

그 다음으로 시작점을 '3'으로 설정해보자. 그럼 자연스럽게 끝점은 '1'이 될 것인데, 이 때, 이 '1'은 13으로 변환할 수가 있다.

그러면 마치 [ 1 , 3 , 4 , 9 , 10 ] 으로 설정되어 있었던 취약점이, [ 3 , 4 , 9 , 10 , 13 ] 으로 설정된 취약점처럼 나타내진다.

여기서 '1'을 '13'으로 변경한 것은, 예제입력2의 n값이 '12'이기 떄문에, 1 + n을 한 값인, 1 + 12 = 13 으로 설정해주면 된다.

[ 3 , 4 , 9 , 10 , 13 ] 의 경우에도 시작점과 끝점간의 거리가 10이기 떄문이 7만큼 움직일 수 있는 친구 혼자서는 해결하지 못한다. 이어서 , '3'을 또 마지막 점으로 넘겨보자.

[ 4 , 9 , 10 , 13 , 15 ]

이 경우에도 마찬가지로 해결하지 못한다. 그럼 '4'를 마지막 점으로 넘겨보자.

[ 9 , 10 , 13 , 15 , 16 ]

이 경우를 한번 보자. 시작점 = 9 이고 끝점 = 16 이기 때문에 둘 사이의 거리가 7이다. 가장 많이 움직일 수 있는 친구의 거리가 7이기 때문에 이 경우에는 별 다른 탐색을 해보지 않아도 저 친구 혼자서 해결을 할 수 있다는 것을 의미한다.

따라서 이 경우에는 바로 return1을 해주면 된다.

본인은 위와 같은 경우를 예외적으로 먼저 처리해주고 본격적인 탐색을 시작하였다.

넘어가기 전에, 여기까지 구현한 코드를 한번 확인해보자.

sort(dist.begin(), dist.end(), Cmp);
vector<int> Temp = weak;
for (int i = 0; i < Temp.size() - 1; i++)
{
    int Start = Temp[0];
    int End = Temp[Temp.size() - 1];
    if (End - Start <= dist[0]) return 1;
    
    int Start_Value = Temp[0];
    for(int j = 1; j < Temp.size(); j++) Temp[j - 1] = Temp[j];
    Temp[Temp.size() - 1] = Start_Value + n;
}

line1) 이 1번 과정, 즉, dist를 내림차순으로 정렬한 과정이다.

line3 ~ 12) 가 본격적인 2번 과정을 나타낸 것이다.

line7)에서 보면, "현재 설정된 시작점과 끝점간의 거리가 가장 많이 움직일 수 있는 친구의 거리보다 작다면" 바로 return 시켜주는 과정이다.

line9 ~ 11)에서는 시작점과 끝점을 계속해서 변경하기 위해서 취약점의 상태를 갱신하는 과정이다.

#3 : 순열 구현

2번 과정에서 정답이 나오지 않았다면, 최소 2명 이상이 필요하다는 것을 의미하고, 본인은 여기서부터 순열을 구현해 주었다. 왜 순열을 구현한지 알아보자.

지금부터는, 점검할 수 있는 친구들을 뽑을 것이다. 뽑아가면서 취약지점을 점검하도록 시킬 것이다. 그런데 왜 순열일까 !

바로 "앞에서 부터 순서대로 취약점을 점검하도록 시킬 것 이기 때문" 이다.

이런 경우를 한번 생각해보자.

.

위와 같은 경우에서 취약지점을 점검하도록 시킨 친구들이 움직일 수 있는 거리가 [ 6 , 4 ] 라고 가정해보자.

간단하게 '1'을 시작점, '13'을 끝점이라고 가정했을 때, 시작점에 '6'인 친구를 집어넣고, 그 이후에 '4'인 친구를 집어 넣었다고 생각해보자. 그럼 '6'인 친구는 1번, 3번, 4번 취약지점을 점검할 것이다. 그럼 그 다음 취약지점인 '8'에 '4'인 친구를 집어넣었다고 가정해보자. '4'인 친구는 남은 취약지점인, 8과 13을 한번에 점검할 수가 없다. 즉 [ 6 , 4 ] 의 순서대로 투입을 하게 되면 한 명이 더 필요한 것 처럼 보이지만, 이 둘의 투입 순서를 바꿔보자. [ 4 , 6 ] 으로 !

그럼 '4'인 친구를 '1'에 집어넣으면, 1번, 3번, 4번 취약지점을 점검할 것이고, 그 다음 취약지점인 '8'에 '6'인 친구를 집어넣으면 '6'인 친구는 남은 취약 지점인 8과 13을 모두 점검할 수가 있다. 즉, [ 6 , 4 ] 로 투입을 할 때와 , [ 4 , 6 ] 으로 투입할 때의 결과가 달라지게 된다.

즉 ! 우리는 점검을 할 친구들을 뽑는데, 순서에 영향을 미치는 "순열을 구현" 해 줘야 하는 것이다.

아직 순열에 대해서 잘 모른다면 아래의 글을 읽고 오도록 하자.

[ 순열에 대해서 알아보기(Click) ]

위의 글을 통해서 혹은 순열에 대해서 알고 있다면, 과연 몇 명을 뽑아야 되는지에 대해서 조금 더 이야기를 해보자.

우리는 2번 과정을 통해서, "2명 이상의 점검자가 필요하다" 라는 것만 알고 있지, 정확하게 몇 명이 더 투입되어야 하는지, 결과적으로 몇 명이 투입되어야 모든 취약점을 다 점검할 수 있는지는 모르는 상태이다.

그래서 본인은 모든 점검자들을 다 뽑아 주었다. 예를 들어서 점검할 수 있는 친구들이 4명이 있다면, 이 4명에 대한 순열을 모두 뽑은 것이다. 그런데 분명히, 4명을 뽑았음에도 2명만 있어도 되는 경우가 존재할 것이다.

그래서 이 경우에 대한 처리하는 과정을 그 다음 과정에서 알아보자.

#4 : 외벽 점검하기

위의 과정에서 우리는 N명의 점검자들을 모두 뽑았고, 그 N명이 이룰 수 있는 모든 순열을 뽑아놓았다.

하지만 반드시 N명이 필요한 것은 아니다. 그 중에 일부만 필요한 경우가 반드시 있을 것이다.

따라서 본인은 N명을 순차적으로 대입해보는 방식으로 진행하였다.

예를 들어서 N명을 '4명'으로 가정하고, 그 4명을 [ A , B , C , D ] 라고 가정해보자.

그럼 취약 지점의 시작점에 'A'를 넣어보고, A가 점검할 수 있는 지점까지 모두 점검을 한다. 그래서 만약, 점검이 다 되지 않았다면, 즉, 취약지점이 더 남았다면 그 이후에 'B'를 넣어보는 것이다.

'B'가 투입됐음에도 취약지점을 다 점검할 수 없어서, 'C'까지 투입했다고 생각해보자. 그런데 ! 'C'를 투입하니까, 드디어 모든 취약지점이 모두 점검되었다고 가정해보자. 그럼 'D'는 어떻게 해야할까 ??

'A', 'B', 'C'로 취약지점을 모두 점검할 수 있다고 해서, 'D'에 대한 탐색을 하지 않아도 되는 것은 아니다.

왜냐하면 우리는 현재 "순열"로 구현되어 있고, 더 이상 "내림차순"으로 정렬된 상태가 아니다. 따라서, 'A', 'B', 'C' 3명에서 점검할 수 있었던 외벽들을, 'C'와 'D' 혹은 'B'와 'D'와 같이 더 적은 인원으로 점검할 수 있는 경우가 존재할 수 있다.

따라서, 만약 "현재 인원으로 취약지점을 모두 점검할 수 있다면 ? 그대로 값만 갱신해주고 계속해서 탐색" 을 해주면 된다.

또한 ! 위에서도 말했지만, 주어진 맵이 원판이다 보니까, 시작점과 끝점을 어떻게 설정하냐에 따라서, 점검에 투입되야 하는 인원수가 달라질 수 있다. 그래서 위에서 했듯이, 시작점과 끝점을 계속해서 바꿔가는 과정 또한 진행해 주어야 한다.

그럼 이 과정을 코드로 한번 확인해보자.

void Check(vector<int> Weak, vector<int> Dist, int N)
{
    for (int i = 0; i < Weak.size() - 1; i++)
    {
        int Weak_Index = 0;
        int Cnt;
        bool Flag = false;
 
        for (int j = 0; (j < V.size()) && (j + 1 < Answer) && (Flag == false); j++)
        {
            int End = Weak[Weak_Index] + Dist[V[j]];
            while (End >= Weak[Weak_Index])
            {
                Weak_Index++;
                if (Weak_Index == Weak.size()) 
                {
                    Cnt = j + 1;
                    Flag = true;
                    break;
                }
            }
        }
        if (Flag == true) Answer = Min(Answer, Cnt);
 
        int Start_Value = Weak[0];
        for (int j = 1; j < Weak.size(); j++) Weak[j - 1] = Weak[j];
        Weak[Weak.size() - 1] = Start_Value + N;
    }
}

이 부분이 본인이 구현한 코드이다.

위의 코드에서 사용된 변수 중, V[] 라는 변수가 있는데, 이 V[]는 순열에서 뽑은 원소들이 순서대로 저장되어 있는 Vector를 의미한다.

먼저 가장 큰 for문인 line3 ~ 28)을 살펴보면, 이 for문은 "외벽의 시작점과 끝점을 계속해서 바꿔가면서 탐색" 하기 위한 for문 이다. 실제로 line 25 ~ 27)을 보게되면, 외벽의 시작점과 끝점을 계속해서 바꿔주는 과정이 있다.

line9 ~ 21) 에 구현되어 있는 for문이 실제로 외벽을 점검하는 과정이라고 볼 수 있다.

line9)에 보면 반복되기 위한 조건이 참 많은데, 조건은 다음과 같이 3가지이다.

1. j < V.size()

- 뽑은 수 만큼만 반복하기 위한 조건이다.

  예를 들어서 N명을 뽑았는데, N + 1명까지 외벽점검에 투입될 수는 없다. 런타임 에러가 발생한다.

2. j + 1 < Answer

- 현재 탐색하면서 인원을 차례대로 뽑을 것인데, 인원을 더 뽑는 순간 "기존에 설정되어 있는 최소 인원보다 더 많다면" 더 이상

  의 탐색은 필요하지 않다. 왜냐하면, 더 많은 인원을 투입해서 외벽을 점검한다고 하더라도, 그 인원수는 기존의 설정되어

  있는 투입되어야 하는 최소 인원수보다 더 많기 때문에 의미없는 탐색이다.

3. Flag = false

- Flag라는 변수는, "외벽을 다 점검할 수 있는지"를 나타내는 변수이다. 만약, 현재 뽑은 인원들 중 일부를 이용해서

  외벽 점검을 모두 마쳤다면, 더 이상의 인원 투입 없이 그 다음 단계로 넘어가면 된다.

  그 다음 단계는 ?? "외벽의 시작점과 끝점을 재설정하는 과정" 을 의미한다.

그래서 line 11 ~ 20) 을 보면, V[]에 저장되어 있는 인원을 한 명씩 뽑으면서 외벽 점검에 투입하는 과정을 나타낸 것이다.

만약, 외벽 점검을 모두 마쳤다면, 즉 line15)에 선언된 조건문에 들어가게 된다면, Cnt라는 변수에 인원을 저장해 주는 것이다.

Cnt = j + 1 인 이유는, V[]에 저장되어 있는 '0번째 사람'을 뽑았다고 하더라도, 실제로 뽑은 인원은 0명이 아닌 1명이기 때문에, 사람 인원수는 j + 1이 되는 것이다.

[ 소스코드 ]

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int Answer = 2e9;
bool Select[8];
vector<int> V;
 
int Min(int A, int B) { if (A < B) return A; return B; }
 
bool Cmp(int A, int B) { if (A > B) return true; return false; }
 
void Check(vector<int> Weak, vector<int> Dist, int N)
{
    for (int i = 0; i < Weak.size() - 1; i++)
    {
        int Weak_Index = 0;
        int Cnt;
        bool Flag = false;
 
        for (int j = 0; (j < V.size()) && (j + 1 < Answer) && (Flag == false); j++)
        {
            int End = Weak[Weak_Index] + Dist[V[j]];
            while (End >= Weak[Weak_Index])
            {
                Weak_Index++;
                if (Weak_Index == Weak.size()) 
                {
                    Cnt = j + 1;
                    Flag = true;
                    break;
                }
            }
        }
        if (Flag == true) Answer = Min(Answer, Cnt);
 
        int Start_Value = Weak[0];
        for (int j = 1; j < Weak.size(); j++) Weak[j - 1] = Weak[j];
        Weak[Weak.size() - 1] = Start_Value + N;
    }
}
 
void DFS(int Cnt, vector<int> Weak, vector<int> Dist, int N)
{
    if (Cnt == Dist.size())
    {
        Check(Weak, Dist, N);
        return;
    }
 
    for (int i = 0; i < Dist.size(); i++)
    {
        if (Select[i] == true) continue;
        Select[i] = true;
        V.push_back(i);
        DFS(Cnt + 1, Weak, Dist, N);
        V.pop_back();
        Select[i] = false;
    }
}
 
int solution(int n, vector<int> weak, vector<int> dist) 
{
    Answer = 2e9;
    sort(dist.begin(), dist.end(), Cmp);
    vector<int> Temp = weak;
    for (int i = 0; i < Temp.size() - 1; i++)
    {
        int Start = Temp[0];
        int End = Temp[Temp.size() - 1];
        if (End - Start <= dist[0]) return 1;
        
        int Start_Value = Temp[0];
        for(int j = 1; j < Temp.size(); j++) Temp[j - 1] = Temp[j];
        Temp[Temp.size() - 1] = Start_Value + n;
    }
 
    DFS(0, weak, dist, n);
    if (Answer == 2e9) return -1;
    return Answer;
}