[PCCP] Lv3: 외벽 점검(60062) 해설

문제

- 문제 링크: 외벽 점검

 

해설

- 자료구조: 

- 시간복잡도: 

 

(풀이과정)

1) 

2) 

3) 

4) 

 

코드

(C언어)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C++)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C#)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(Java)

solution 1)

- N: dist의 길이

- M: weak의 길이

- weak 리스트에 항목을 추가하는 연산: O(M)

- 이후 반복문에서 모든 weak 지점을 순회(M)하며 친구들의 순열을 모두 확인(N!)

- 현재 투입된 친구가 다음 weak까지 갈 수 있는지 체크하기 위한 시간 복잡도는 M이므로 최종 시간 복잡도는 O(M^2 * N!)

import java.util.Arrays;

class Solution {
    private static int length, answer;
    private static int[] Weak;
    private static boolean[] used;
    
    // dist 배열의 친구들로 모든 외벽이 점검 가능한지 확인
    private static boolean check(int[] dist) {
        // 점검을 시작하는 외벽을 0부터 length까지 전부 확인함
        for (int i = 0; i < length; ++i) {
            int idx = i;
            // 각 친구가 점검 가능한 외벽을 모두 점검하여 진행
            for (int distance : dist) {
                int position = Weak[idx++] + distance;
                while (idx < Weak.length && Weak[idx] <= position) {
                    idx++;
                }
            }
            // 모든 외벽을 점검 가능하면 true 반환
            if (idx - i >= length)
                return true;
        }
        // 모든 외벽을 점검할 수 없으면 false 반환
        return false;
    }
    
    // n개의 숫자를 나열하는 모든 경우의 수를 구함
    private static void backtrack(int n, int[] dist, int[] org) {
        if (n == org.length) {
            // 모든 외벽이 점검 가능하면 답을 저장
            if (check(dist))
                answer = n;
            return ;
        }
        
        // 한 번 사용한 친구는 다시 사용하지 않도록 used 배열을 활용하여 백트래킹
        for (int i = 0; i < org.length; ++i) {
            if (!used[i]) {
                used[i] = true;
                dist[n] = org[i];
                backtrack(n + 1, dist, org);
                used[i] = false;
            }
        }
    }
    
    public static int solution(int n, int[] weak, int[] dist) {
        // 주어진 weak 지점들을 선형으로 만들어 줌
        length = weak.length;
        Weak = new int[length * 2];
        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < length; ++j) {
                Weak[j + (i * length)] = weak[j] + (i * n);
            }
        }
        
        // 오름차순으로 정렬
        Arrays.sort(dist);
        answer = -1; // 답을 -1로 초기화
        used = new boolean[dist.length]; // used 배열 생성
        
        // 가장 점검 번위가 큰 친구부터 1명씩 늘려가며 답을 탐색
        for (int i = 1; i <= dist.length; ++i) {
            int[] org = new int[i];
            System.arraycopy(dist, dist.length - i, org, 0, i);
            backtrack(0, new int[i], org);
            if (answer > 0) // 답을 찾았으면 종료해야 함
                break;
        }
        return answer;
    }
}

solution 2)

#include<>

solution 3)

#include<>

 

(Python)

solution 1)

- N: dist의 길이

- M: weak의 길이

- weak 리스트에 항목을 추가하는 연산: O(M)

- 이후 반복문에서 모든 weak 지점을 순회(M)하며 친구들의 순열을 모두 확인: O(N!)

- 현재 투입된 친구가 다음 weak까지 갈 수 있는지 체크: O(M)

- 최종 시간 복잡도: O((M^2) * N!)

from itertools import permutations

def solution(n, weak, dist):
    # 주어진 weak 지점들을 선형으로 만들기 위해 weak 리스트에 마지막 지점 + n을 추가
    length = len(weak)
    for i in range(length):
        weak.append(weak[i] + n)
    
    # 투입할 수 있는 친구들의 수에 1을 더한 값을 초기값으로 설정
    answer = len(dist) + 1
    
    # 모든 weak 지점을 시작점으로 설정하며 경우의 수 탐색
    for i in range(length):
        for friends in permutations(dist, len(dist)):
            # friends에 들어 있는 친구들을 순서대로 배치하며 투입된 친구 수(cnt) 측정
            cnt = 1
            position = weak[i] + friends[cnt - 1]
            # 현재 투입된 친구가 다음 weak 지점까지 갈 수 있는지 검사
            for j in range(i, i + length):
                if position < weak[j]:
                    cnt += 1
                    # 투입 가능한 친구의 수를 초과한 경우 탐색 중단
                    if cnt > len(dist):
                        break
                    position = weak[j] + friends[cnt - 1]
            # 최소 친구수를 구한
            answer = min(answer, cnt)
            
    # 모든 경우의 수를 탐색한 결과가 투입 가능한 친구 수를 초과하는 경우, -1 반환
    return answer if answer <= len(dist) else -1

solution 2)

import

solution 3)

import

 

(JavaScript)

solution 1)

- N: dist의 길이

- M: weak의 길이

- weak 배열에 항목을 추가하는 연산: O(M)

- 반복문에서 모든 weak 지점을 순회(M)하며 친구들의 순열을 모두 확인: O(N!)

- 현재 투입된 친구가 다음 weak까지 갈 수 있는지 체크: O(M)

- 최종 시간 복잡도: O(M^2 * N!)

function permutations(arr, n) {
    // 더 이상 뽑을 수 없다면 반환하여 탈출 조건으로 사용
    if (n === 0) 
        return [[]];
        
    const result = [];
    
    // 요소를 순환
    arr.forEach((fixed, idx) => {
        // 현재 요소를 제외한 나머지 요소들을 복사
        const rest = [...arr];
        rest.splice(idx, 1);
        
        // 나머지 요소들로 순열 구함
        const perms = permutations(rest, n - 1);
        
        // 나머지 요소들로 구한 순열에 현재 요소를 추가
         const combine = perms.map((p) => [fixed, ...p]);
         
         // 결과에 추가
         result.push(...combine);
    });
    
    return result;
}

function solution(n, weak, dist) {
    // 주어진 weak 지점들을 선형으로 만들기 위해 weak 배열에 마지막 지점 + n을 추가
    const length = weak.length;

    for (let i = 0; i < length; ++i) {
        weak.push(weak[i] + n);
    }

    // 투입할 수 있는 친구들의 수에 1을 더한 값을 초기값으로 설정
    let answer = dist.length + 1;
    
    // 모든 weak 지점을 시작점으로 설정하여 경우의 수를 탐색
    for (let i = 0; i < length; ++i) {
        for (const friends of permutations(dist, dist.length)) {
            // friends에 들어있는 친구들을 순서대로 배치하여 투입된 친구 수(cnt) 측정
            let cnt  = 1;
            let position = weak[i] + friends[cnt - 1];
            
            // 현재 투입된 친구가 다음 weak 지점까지 갈 수 있는지 검사
            for (let j = i; j < i + length; ++j) {
                if (position < weak[j]) {
                    cnt +=1;
                    // 투입 가능한 친구의 수를 초과한 경우 탐색 중단
                    if (cnt > dist.length) {
                        break;
                    }
                    position = weak[j] + friends[cnt - 1];
                }
            }
            // 최소 친구 수를 구함
            answer = Math.min(answer, cnt);
        }
    }

    // 모든 경우의 수를 탐색한 결과가 투입 가능한 친구 수를 초과하는 경우, -1 반환
    return answer <= dist.length ? answer : -1;
}

solution 2)

import

solution 3)

import