외벽 점검 - 2020 카카오 공채 (python)

프로그래머스, 2020 카카오 공채 코딩테스트 기출 - 외벽 점검 LV3
https://programmers.co.kr/learn/courses/30/lessons/60062
모든 경우의 수리 형태를 조사하는 완전탐색 문제
set, 혹은 permutation 사용

👀 깃헙 소스

외벽의 길이 n, 취약 지점의 위치가 담긴 배열 weak, 각 친구가 1시간 동안 이동할 수 있는 거리가 담긴 배열 dist가 매개변수로 주어질 때, 취약 지점을 점검하기 위해 보내야 하는 친구 수의 최소값을 return 하도록 solution 함수를 완성해주세요.

입출력 예

n	weak		dist		result
12	[1, 5, 6, 10]	[1, 2, 3, 4]	2

솔루션
선형형태로 weak 변형, 혹은 %를 이용, 둘 다 완전탐색 방식
1) permutation을 사용하여 친구들 차례로 벽에 위치 시킨 후 조건 만족시 cand에 추가
2) dist가 큰 친구부터 차례로 위치 시킴 set 이용하여 모든 취약 지점이 수리 되었는지 확인
결론적으로 방법2가 훨씬 더 시간효율은 높음.

# 선형형태로 변경된 weak_point
[1, 5, 6, 10, 13, 17, 18, 22]

# permutations(dist)
[(1, 2, 3, 4), (1, 2, 4, 3), (1, 3, 2, 4),  ... ]

코드

방법 1) permutation을 사용하여 친구들 차례로 벽에 위치 시킨 후 조건 만족시 cand에 추가

# 파이썬
from itertools import permutations
def solution(n, weak, dist):
    L = len(weak)
    cand = []
    weak_point = weak + [w+n for w in weak]  # 선형으로

    for i, start in enumerate(weak):
        for friends in permutations(dist):  # 순열 이용
            count = 1
            position = start
            # 친구 조합 배치
            for friend in friends:
                position += friend
                # 끝 포인트까지 도달 못했을 때
                if position < weak_point[i+L-1]:
                    count += 1  # 친구 더 투입
                    # 현재 위치보다 멀리 있는 취약지점 중 가장 가까운 위치로
                    position = [w for w in weak_point[i+1:i+L]
                                if w > position][0]
                else:  # 끝 포인트까지 도달
                    cand.append(count)
                    break

    return min(cand) if cand else -1

방법 2) dist가 큰 친구부터 차례로 위치 시킴 set 이용하여 모든 취약 지점이 수리 되었는지 확인

# 파이썬
def solution(n, weak, dist):

    W, F = len(weak), len(dist)
    repair_lst = [()]  # 현재까지 고칠 수 있는 취약점들 저장 (1,2,3)
    count = 0  # 투입친구 수
    dist.sort(reverse=True) # 움직일 수 있는 거리가 큰 친구 순서대로

    # 고칠 수 있는 것들 리스트 작성
    for can_move in dist:
        repairs = []  # 친구 별 고칠 수 있는 취약점들 저장
        count += 1

        # 수리 가능한 지점 찾기
        for i, wp in enumerate(weak):
            start = wp  # 각 위크포인트부터 시작
            ends = weak[i:] + [n+w for w in weak[:i]]  # 시작점 기준 끝 포인트 값 저장
            can = [end % n for end in ends if end -
                   start <= can_move]  # 가능한 지점 저장
            repairs.append(set(can))

        # 수리 가능한 경우 탐색
        cand = set()
        for r in repairs:  # 새친구의 수리가능 지점
            for x in repair_lst:  # 기존 수리가능 지점
                new = r | set(x)  # 새로운 수리가능 지점
                if len(new) == W:  # 모두 수리가능 한 경우 친구 수 리턴
                    return count
                cand.add(tuple(new))
        repair_lst = cand

    return -1

주의 :
1) 집합에 집합을 넣을 수 없으므로 tuple로 변경해서 넣음
2) 초기화를 set이 아닌 repair_lst = [()] 로 하는 이유는 for x in repair_lst: # 기존 수리가능 지점 new = r | set(x) 부분에서 처음에 스킵되지 않고 공집합과의 합집합된 것이 적용되어야 하기 때문