[카카오 2020 공채] 외벽 점검

카카오 2020 공채 외벽 점검 해설입니다

브루트 포스 알고리즘을 통해 해결할 수 있는 문제입니다. 문제 해결의 핵심 조건들은 다음과 같습니다

• 레스토랑의 구조는 완전히 동그란 모양이다
• 외벽의 총 둘레는 n 미터이다

레스토랑의 구조가 원형이기 때문에 Circular Array로 접근해야 합니다. 그리고 이동 방향이 시계 방향이든 반시계 방향이든 중요하지 않습니다.

레스토랑이 원형이기 때문에 10 -> 1 -> 5 -> 6 이던 5 -> 1 -> 10 -> 6 이던 동일하기 때문입니다.

이제 외벽을 점검할 친구들을 골라야합니다. 그런데 당연하게 이동거리가 큰 친구들을 먼저 사용하면 최대한 적은 친구들을 동원할 수 있을 것 입니다. 따라서 dist 배열을 정렬합니다.

그리고 수리할 취약 지점의 순서를 permutate 알고리즘을 통해 구하고, 동원할 친구들의 최소값을 찾습니다.

먼저 Java 코드를 분석해보겠습니다.
permutate() 메소드는 동원한 친구의 수(n), 현재 수리할 취약 지점의 위치(current), 이미 방문한 취약 지점들(visited)를 인자로 가집니다. weak point가 15보다 크지 않으므로 visited는 비트 연산으로 진행하겠습니다.

static final int INF = Integer.MAX_VALUE;
int N, minCount;
int[] Weak;
int[] Dist;
public int solution(int n, int[] weak, int[] dist) {
    N = n;
    Weak = weak;
    Dist = dist;
    minCount = INF;
    Arrays.sort(dist);
    for (int i=0;i<Weak.length;i++) {
        permutate(1, i, 0);
    }

    return minCount == INF ? -1 : minCount;
}

전달할 인자의 수를 줄이기 위해, 초기에 주어지는 값 들은 모두 전역 변수로 하겠습니다. 그리고 출발 지점을 달리하여 permutate() 메소드를 호출합니다.

public void permutate(int cnt, int current, int visited) {
    if (cnt >= minCount || cnt > Dist.length)
        return;
    ...    

현재 동원한 친구들의 수(cnt)가 최소 인원 보다 크거나 같으면 더이상 볼 필요도 없습니다. 그리고 동원한 친구의 수가 현재 존재하는 모든 친구보다 클 수 없습니다.

public void permutate(int cnt, int current, int visited) {
    ...    

    for (int i = 0;i < Weak.length;i++) {
        int next = (current + i) % Weak.length; // Circular
        int diff = Weak[next] - Weak[current]; // 다음 취약지점 까지의 거리

        if (next < current)
            diff += N;

        if (diff > Dist[Dist.length - cnt]) // 다음 취약 지점까지의 거리가 현재 친구의 최대 이동거리보다 큰 경우 
            break;

        visited |= (1 << next); // 방문 체크
    }
   ...

next는 다음에 수리할 외벽을 가리키는 포인터입니다.

int next = (current + i) % Weak.length; 는 다음 포인터가 n을 넘어가는 경우를 의미합니다. 그림으로 표현하면 아래와 같습니다

따라서 weak의 길이 만큼 나머지 연산하여 Circular Array의 인덱스를 구해준 것 입니다

if (next < current) 은 위 그림과 같이 next가 current보다 값이 더 작아진 경우를 의미합니다. 이때 diff에 weak의 크기인 N을 더해주어 current - next 간의 거리를 구한 것 입니다.

그리고 다음 취약 지점까지의 거리가 현재 친구가 이동할 수 있는 거리 보다 더 먼 경우에는 방문한 지점으로 체크하지 않고 종료합니다.

public void permutate(int cnt, int current, int visited) {
    ...    

    if (visited == (1 << Weak.length) - 1) { // 모두 방문한 경우
        minCount = cnt;
        return;
    }

    for (int i = 0;i < Weak.length;i++) {
        if ((visited & (1 << i)) != 0) continue;

        permutate(cnt + 1, i, visited); // 방문하지 않은 곳 방문
    }

모든 취약 지점을 방문한 경우, minCount를 업데이트 합니다. 여기서 최소 비교를 하지 않는 이유는 이미 가장 처음에 cnt가 minCount보다 크거나 같은 경우는 처리했기 때문입니다.

자바 코드 분석은 끝났습니다. 하지만 위 코드를 파이썬 코드에 적용하면 시간초과가 발생합니다. 따라서 파이썬 코드도 분석해보겠습니다. 전체적인 로직은 동일합니다.

파이썬에서는 효율적인 브루트포스를 위해 itertools의 permutations() 함수를 사용하겠습니다.

 for start in range(len(weak)): #1
        for d in permutations(dist):#2
            current = start
            cnt = 1
            for i in range(len(weak)):#3
                _next = (start + i) % len(weak) #4
                diff = weak[_next] - weak[current]

                if _next < current:
                    diff += n

                if diff > d[cnt - 1]: #5
                    current = _next
                    cnt += 1
                    if cnt > len(dist) or cnt >= min_count:#6
                        break

            if cnt <= len(dist) and cnt < min_count:#7
                min_count = cnt

• #1은 취약지점을 모두 방문해보기 위한 반복문입니다.
• #2는 동원 친구들의 모든 경우의 수를 구하기 위해 permutations()를 사용했습니다.
• #3에서 모든 취약지점을 start 부터 원형으로 방문하기 시작합니다.
• #4는 Circual Array에서 인덱스 처리입니다
• #5은 cnt는 1부터 시작했기 때문에 -1을 더해주었고, 현재 친구의 이동할 수 있는 거리보다 다음 취약점 거리가 더 먼 경우입니다
  • 이 경우 동원할 친구 한명을 더 늘리고, 친구가 취약지점을 점검하기 시작한 위치를 다음 친구가 취약 지점을 점검할 위치로 변경합니다.
  • 만일 #5의 조건을 만족하지 않았다면, 현재 친구가 다음 취약지점도 점검 가능한 것입니다.
• #6에서 현재까지 동원한 친구의 수가 최소 동원수 보다 이미 크거나, 최대한 동원할 친구의 수보다 큰 경우 다음은 볼 필요가 없기 때문에 종료합니다.
• #7 min_count를 업데이트 합니다.

Java

import java.util.*;
class Solution {
    static final int INF = Integer.MAX_VALUE;
    int N, minCount;
    int[] Weak;
    int[] Dist;
    public int solution(int n, int[] weak, int[] dist) {
        N = n;
        Weak = weak;
        Dist = dist;
        minCount = INF;
        Arrays.sort(dist);
        for (int i=0;i<Weak.length;i++) {
            permutate(1, i, 0);
        }

        return minCount == INF ? -1 : minCount;
    }

    public void permutate(int cnt, int current, int visited) {
        if (cnt >= minCount || cnt > Dist.length)
            return;

        for (int i = 0;i < Weak.length;i++) {
            int next = (current + i) % Weak.length;
            int diff = Weak[next] - Weak[current];

            if (next < current)
                diff += N;

            if (diff > Dist[Dist.length - cnt])
                break;

            visited |= (1 << next);
        }

        if (visited == (1 << Weak.length) - 1) {
            minCount = cnt;
            return;
        }

        for (int i = 0;i < Weak.length;i++) {
            if ((visited & (1 << i)) != 0) continue;

            permutate(cnt + 1, i, visited);
        }
    }
}

Python

from itertools import permutations

def solution(n, weak, dist):
    INF = float('inf')
    min_count = INF

    for start in range(len(weak)):
        for d in permutations(dist):
            current = start
            cnt = 1
            for i in range(len(weak)):
                _next = (start + i) % len(weak)
                diff = weak[_next] - weak[current]

                if _next < current:
                    diff += n

                if diff > d[cnt - 1]:
                    current = _next
                    cnt += 1
                    if cnt > len(dist) or cnt >= min_count:
                        break

            if cnt <= len(dist) and cnt < min_count:
                min_count = cnt

    return min_count if min_count != INF else -1