[프로그래머스]2020 KAKAO BLIND RECRUITMENT : 외벽 점검 (level 3)(c++)

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

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

 

브루트포스, 순열

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

using namespace std;

int solution(int n, vector<int> weak, vector<int> dist) {

    // 순열을 위해 dist정렬
    sort(dist.begin(), dist.end());

    int w_size = weak.size();
    int d_size = dist.size();
    int answer = -1;

    // 원형탐색을 위해 weak벡터 뒤쪽에 각 요소보다 n씩 큰 요소 추가
    for (int i = 0; i < w_size; ++i)
    {
        weak.push_back(weak[i] + n);
    }

    // 원형탐색: w_idx부터 탐색 시작
    for (int w_idx = 0; w_idx < w_size; ++w_idx)
    {
        /*
            ex) n = 50, weak = [1, 5, 10, 16, 22, 25], dist = [3, 4, 6] 의 경우
                4:(1, 5),  6:(10, 16),  3:(22, 25) 만이 가능하다.
                
            따라서 dist벡터 내림차순 정열을 이용한 그리디기법은 사용할 수 없고 완전탐색이 필요하다
        */
        do {
            
            int passed = 0;
            int d_idx = 0;

            // weak과 dist의 인덱스가 범위 하에 있으면
            while (d_idx < d_size && passed < w_size)
            {
                // 친구가 최대로 닿을 수 있는 지점
                int end = weak[w_idx + passed] + dist[d_idx];

                // 그 사이에 있는 취약지점은 방문 완료 처리
                while (passed < w_size && weak[w_idx + passed] <= end)
                {
                    ++passed;
                }
                ++d_idx;
            }

            // 모든 취약지점을 다 방문했을 때 : 가장 적은 파견 친구수 갱신
            if (passed == w_size)
            {
                answer = (answer < 0) ? d_idx : min(d_idx, answer);
            }
        
        } while (next_permutation(dist.begin(), dist.end()));
    }

    return answer;
}

 

 

2020공채 1차 문제 중에서 제일 정답율이 낮았던 문제였다.

하지만 대단히 어려운 알고리즘은 사용되지 않는 문제였다.

문제를 읽고 브루트포스로 풀어야겠다고 생각하는 과정이 어려웠던 것 같다.

 

 

이 문제의 포인트는 다음과 같다. 

1. 원형탐색 : 취약지점 탐색

2. 브루트포스 : 친구를 파견하는 경우의 수

 

 

1. 원형탐색 : 취약지점 탐색

원형탐색을 해결하는 방법은 여러가지가 있다. 

a. weak벡터의 길이를 2배 늘려 다음 요소를 뒤쪽에 추가하기

b. 매 회 weak벡터의 요소들을 한칸씩 옮기기

 

weak의 길이는 최대 15로 그리 크지 않지만

b방법처럼 시간복잡도 O(n)을 계산에 추가하는 것 보다는

a방법으로 공간을 조금 더 쓰는게 낫다고 생각한다.

// 원형탐색을 위해 weak벡터 뒤쪽에 각 요소보다 n씩 큰 요소 추가
for (int i = 0; i < w_size; ++i)
{
    weak.push_back(weak[i] + n);
}

 

 

 

2. 브루트포스 : 친구를 파견하는 경우의 수

처음에는 dist벡터를 내림차순으로 정렬하여 그리디로 풀려고 시도했다.

그런데 자꾸 몇가지 테케에서 오류가 나서 찾아보니..

int n = 50; 
vector<int> weak = { 1, 5, 10, 16, 22, 25 }; 
vector<int> dist = { 3, 4, 6 };

// 답 : 3
// 4:(1, 5),  6:(10, 16),  3:(22, 25)

그리디로는 위와 같은 경우를 잡아낼 수 없다. 

 

그래서 브루트포스로 풀어야 모든 경우의 수를 구할 수 있고,

마찬가지로 dist 벡터의 길이가 최대 8이라서 O(N * N!)인 permutation 연산이 무리가 없다.

 

 

 

풀이를 참고한 블로그

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

 

[Python] 프로그래머스. 2020 카카오 recruit - 외벽 점검 (Level 3)