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

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

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

 

✅ 풀이

from itertools import permutations

def solution(n, weak, dist):
    answer = 9                   # 1)
    _len = len(weak)
    
    for i in range(_len):        # 2)
        weak += [weak[i] + n]
        
    
    # 3) 모든 취약점 위치를 시작점으로 하여 각 친구가 취약 지점들을 커버할 수 있는지 확인함
    for i in range(_len):
        for friend in permutations(dist, len(dist)):
            cnt = 1
            pos = weak[i] + friend[cnt - 1]    # 첫번째 친구가 i 위치의 취약점에서 이동할 수 있는 거리
            for j in range(i, i + _len):
                if pos < weak[j]:       # i 이후의 각 취약점을 현재 친구가 커버할 수 없으면, 친구를 추가 투입해야함
                    cnt += 1
                    if cnt > len(dist):
                        break
                        
                    pos = weak[j] + friend[cnt-1]
                    
            answer = min(answer, cnt)
    
    return answer if answer <= len(dist) else -1

 

1) answer = 9

친구 수의 최소값을 구하는데, 각 친구마다 이동할 수 있는 거리가 담긴 배열인 dist의 길이가 1이상 8이하 이므로 answer = 9로 설정한다.

 

2) 이부분은 기존의 취약점 위치를 나타내는 배열인 weak의 길이를 2배 확장하는 코드이다. 

 

예를들어 첫번째 예시인 weak = [1, 5, 6, 10] 에서 10m 지점에서 취약점을 점검한다고 했을 때, 4m를 이동할 수 있는 친구는 취약점 1을 점검할 수 있다. 1의 경우 시계 방향으로 회전한다고 했을 때, 1 + 12 = 13으로 이동한다고 가정하면 편하다.

 

따라서 원으로 시계 방향 혹은 반시계 방향으로 회전하면서 취약점 점검을 하기 때문에 회전한다는 동작을 고려하여 각각의 취약점에 n을 더하여 길이를 확장한다.

 

3) 이제 모든 취약점의 위치를 시작으로 하여 친구들의 순서에 따라 취약 점검에 필요한 친구가 몇명 필요한지 계산한다.

이때 어떤 순서로 친구가 취약점을 점검하느냐에 따라 필요한 친구 수가 달라지기 때문에, 조합이 아닌 순열(permutations)로 처리한다.

 

첫번째 취약점에서 시작하기 때문에, 필요한 친구수(cnt)를 초기값으로 1로 세팅한다.

그리고 친구가 이동할 수 있는 거리를 이동하며, 거리에 닿지 못하는 경우 해당 취약점을 점검하지 못한다는 의미이므로 친구 수를 늘리며

필요한 친구 수의 최소값을 계산해 나간다.

 

 

✅ 다른 풀이

def solution(n, weak, dist):

    W = len(weak)
    repair_lst = [()]  # 현재까지 고칠 수 있는 취약점들 저장하는 리스트
    count = 0
    dist.sort(reverse=True)  # 1) 커버 범위가 넓은 친구부터 적용하기 위해 내림차순 정렬함

    for i in range(W):        
        weak += [weak[i] + n]
        
    for can_move in dist:
        repairs = []    # 각 친구마다 커버할 수 있는 취약 범위들을 저장하기 위한 리스트
        count += 1

        for i in range(W):    # 각 취약점마다 시작해서 취약점들을 점검할 수 있는 범위를 찾기 위함
            start = weak[i]
            can = set()
            # start 기준으로 시계 방향으로 can_move 내에 있는 weak 찾기
            for j in range(i, i + W):
                if weak[j] - start <= can_move:
                    can.add(weak[j] % n)
            repairs.append(can)

        # 가능한 모든 기존 조합과 병합
        cand = set()
        for r in repairs:           # 각 취약점 조합
            for x in repair_lst:     # 지금까지의 커버 가능한 취약점 조합
                new = set(x) | r
                if len(new) == W:
                    return count
                cand.add(tuple(new))
        repair_lst = cand

    return -1

 

완전탐색 + 그리디로 풀 수 있는 풀이이다.

 

1) dist.sort(reverse=True)를 통해 가장 멀리갈 수 있는 (커버 범위가 넓은) 친구부터 접근해야 투입할 수 있는 친구의 수가 적어지기 때문에, 내림차순 정렬한다.

 

2) 아래와 같이 각 친구마다 각 취약점에서 시작할 때마다 커버할 수 있는 지점의 조합을 구한다.

    for can_move in dist:
        repairs = []    # 각 친구마다 커버할 수 있는 취약 범위들 조합을 저장하기 위한 리스트
        count += 1

        for i in range(W):    # 각 취약점마다 시작해서 취약점들을 점검할 수 있는 범위를 찾는다.
            start = weak[i]
            can = set()
            # start 기준으로 시계 방향으로 can_move 내에 있는 weak 찾기
            for j in range(i, i + W):
                if weak[j] - start <= can_move:
                    can.add(weak[j] % n)
            repairs.append(can)

 

 

3) 위에서 구한 커버 가능한 취약점과 기존 다른 친구들이 커버한 취약점 조합들을 차례로 합하며 (합집합 -> |) 기존의 취약점의 길이(len(dist))와 같으면 친구수를 return하고 종료한다.

그게 아니라면, 계속 조합을 합치며 비교해야하므로 set에 해당 조합을 저장한다.

    for can_move in dist:
    
      """
      위와 동일
      """
    
        # 가능한 모든 기존 조합과 병합
        cand = set()
        for r in repairs:           # 각 취약점 조합
            for x in repair_lst:     # 지금까지의 커버 가능한 취약점 조합
                new = set(x) | r
                if len(new) == W:
                    return count
                cand.add(tuple(new))
        repair_lst = cand

    return -1