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

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

프로그래머스

---

'''

    Chapter 12. 외벽 점검

    접근법 1

        취약 지점 최대 15, 친구 수 최대 8 -> 완전 탐색

        투입할 친구 순서, 점검 시작 위치를 정하기

        친구를 투입 시작

            마지막 투입된 친구가 끝까지 확인 가능하면 멈추기

            마지막까지 확인이 불가능하면 점검위치를 아직 확인 못한 취약 지점 중 가장 가까운 곳으로 바꾸고 반복

'''

from itertools import permutations

def solution(n, weak, dist):
    m = len(weak)
    answer = len(dist)+1
    # 원형을 선형으로
    weak = weak + [num+n for num in weak]
    
    # 투입될 친구 순서
    for friends in permutations(dist):
        # 점검 시작 위치
        for idx in range(m):
            new_weak = weak[idx:idx+m]
            now = new_weak[0]
            # 점검 시작
            # 친구 수
            f_cnt = 0
            for f in friends:
                f_cnt += 1
                
                # 최소가 아니면 멈추기
                if f_cnt >= answer:
                    break
                now = now + f
                
                # 끝까지 점검했는가?
                if now >= new_weak[-1]:
                    answer = f_cnt
                    break
                else:
                    # 다음 점검 위치 == 아직 확인 못한 취약 지점 중 가장 가까운 곳
                    for w in new_weak:
                        if w > now:
                            now = w
                            break
                
    if answer > len(dist):
        return -1
    else:
        return answer

'''

테스트 1 〉 통과 (0.03ms, 10.1MB)

테스트 2 〉 통과 (0.03ms, 10.1MB)

테스트 3 〉 통과 (990.52ms, 10.2MB)

테스트 4 〉 통과 (922.70ms, 10.3MB)

테스트 5 〉 통과 (1.41ms, 10.2MB)

테스트 6 〉 통과 (132.37ms, 10.1MB)

테스트 7 〉 통과 (0.04ms, 10.2MB)

테스트 8 〉 통과 (0.18ms, 10.1MB)

테스트 9 〉 통과 (0.36ms, 9.97MB)

테스트 10 〉    통과 (887.75ms, 10.2MB)

테스트 11 〉    통과 (1108.14ms, 10.2MB)

테스트 12 〉    통과 (985.65ms, 10.1MB)

테스트 13 〉    통과 (1420.69ms, 10.1MB)

테스트 14 〉    통과 (1129.67ms, 10.2MB)

테스트 15 〉    통과 (956.84ms, 10.3MB)

테스트 16 〉    통과 (487.59ms, 10.3MB)

테스트 17 〉    통과 (818.16ms, 10.2MB)

테스트 18 〉    통과 (732.21ms, 10.2MB)

테스트 19 〉    통과 (383.23ms, 10.1MB)

테스트 20 〉    통과 (474.84ms, 10.3MB)

테스트 21 〉    통과 (518.72ms, 10.2MB)

테스트 22 〉    통과 (0.23ms, 10.1MB)

테스트 23 〉    통과 (0.26ms, 10.2MB)

테스트 24 〉    통과 (0.47ms, 10.1MB)

테스트 25 〉    통과 (304.42ms, 10.3MB)

'''

 

---

'''

    접근법 2

        완전 탐색하니 시간이 너무 많이 걸린다 -> 최소인원으로 탐색해보고 점검 가능하면 return

        투입할 친구 순서+수, 점검 시작 위치 정하기

        투입할 친구를 거리가 가장 먼 친구들 i명 뽑아서 순열

        ex) 친구 = [1,2,3,4]일 때 1명만 탐색가는 경우 [4]로 해결이 안되면 [1],[2],[3]도 해결이 안됨

        i번 친구 투입

            남아있는 지점 중 첫번째 지점 ~ 첫번째 지점 + 친구 이동거리

            위 범위에 있는 취약 지점은 i번 친구가 해결

'''

from itertools import permutations

def solution(n, weak, dist):
    # 가장 멀리 갈 수 있는 친구 순으로
    dist.sort(reverse=True)
    
    len_weak = len(weak)
    # 원형 -> 선형으로
    weak = weak + [num+n for num in weak] 
    
    for i in range(1,len(dist)+1):
        # 거리가 먼 친구순으로 i명 선택 -> 그 친구들을 순서 섞기
        for ff in permutations(dist[:i]):
            # 점검 시작점
            for idx in range(len_weak):
                friends = list(ff[:])
                new_weak = weak[idx:idx+len_weak]

                # 점검
                while friends and new_weak:
                    # 이번에 점검할 친구가 움직일 거리
                    f = friends.pop(0)
                    # 이번에 점검할 지점 위치
                    w = new_weak.pop(0)
                    # 친구가 점검 끝났을 때 위치
                    current = f+w

                    # w와 current 사이에 있는 지점은 f 친구가 다 점검함
                    while new_weak and new_weak[0] <= current:
                        new_weak.pop(0)
                
                # 다 점검했으면
                if len(new_weak) == 0:
                    return i
    return -1

'''

테스트 1 〉 통과 (0.02ms, 10.1MB)

테스트 2 〉 통과 (0.02ms, 10.2MB)

테스트 3 〉 통과 (1074.79ms, 10.2MB)

테스트 4 〉 통과 (957.97ms, 10.3MB)

테스트 5 〉 통과 (0.49ms, 10.2MB)

테스트 6 〉 통과 (0.91ms, 10.3MB)

테스트 7 〉 통과 (0.02ms, 10.2MB)

테스트 8 〉 통과 (0.04ms, 10.2MB)

테스트 9 〉 통과 (0.08ms, 10.2MB)

테스트 10 〉    통과 (4.71ms, 10.4MB)

테스트 11 〉    통과 (27.57ms, 10.3MB)

테스트 12 〉    통과 (7.57ms, 10.2MB)

테스트 13 〉    통과 (1843.46ms, 10.2MB)

테스트 14 〉    통과 (30.94ms, 10.4MB)

테스트 15 〉    통과 (4.73ms, 10.1MB)

테스트 16 〉    통과 (0.07ms, 10.3MB)

테스트 17 〉    통과 (0.93ms, 10.2MB)

테스트 18 〉    통과 (0.22ms, 10.3MB)

테스트 19 〉    통과 (0.04ms, 10.2MB)

테스트 20 〉    통과 (0.13ms, 10.3MB)

테스트 21 〉    통과 (0.03ms, 10.2MB)

테스트 22 〉    통과 (0.12ms, 10.3MB)

테스트 23 〉    통과 (0.44ms, 10.4MB)

테스트 24 〉    통과 (0.66ms, 10.2MB)

테스트 25 〉    통과 (2.31ms, 10.2MB)

'''