외벽 점검

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

프로그래머스

---

try1

일단 모든 weak를 볼 수 있을 때까지 점검에 투입하는 작업자 수를 하나씩 늘리면서,

itertools의 combinations을 이용하여 모든 경우의 수를 보려함

그리고 시계방향만 확인하려함

 

※ 나의 코드

from itertools import combinations

def solution(n, weak, dist):
    for d in range(len(dist)):           # 점검자 수를 늘려가는 for문
        start_list = list(combinations((weak),d+1)) # 점검자 수에 따른 점검 시작 위치들을 담음
        
        for start in start_list:
            id_list = []
            for s in start:
                id_list += [weak.index(s)]      # weak에서의 점검 시작 위치 인덱스를 담음
                
            copy_dist = dist.copy()
            
            for id, value in enumerate(id_list):
                if value == id_list[-1]:           # 점검자 중 마지막으로 확인 하는 사람이라면
                    check_weak = weak[value:] + weak[:id_list[0]]
                else:                              # 아니라면
                    next = id_list[id + 1]
                    check_weak = weak[value:next]
                    
                if check_weak[0] == min(check_weak):  # 해당 점검자의 점검 순서가 오름차순으로 되어있다면
                    length = (check_weak[-1] - check_weak[0])
                else:                                 # 아니라면
                    length = (n - (check_weak[0] - check_weak[-1]))
                    
                for cd in copy_dist:
                    if cd >= length:     # 해당 점검이 가능하다면 해당 점검자를 남은 점검자에서 제거
                        copy_dist.remove(cd)
                        break                       
                else:
                    break       # 해당 점검이 불가능하다면 다음 점검 시작 위치를 확인함
                    
            else:        # 모든 점검이 가능하다면
                return d+1
    return -1       # 모든 경우의 수가 점검이 불가능하다면

문제풀이)

dist의 길이가 가능한 점검자 수이므로 combinations을 이용하여 첫번째 for문에서 1명부터 가능한 점검자 수까지의 점검 시작 위치들을 start_list에 담음

그 다음 이중 for문을 통하여 확인하려는 시작 위치들이 weak에서의 index가 몇인지 id_list에 담음

남은 가능한 점검자를 확인하기 위한 copy_dist를 만듦

다음 for-else문에서 마지막으로 점검하는 사람이라면 if문을 그렇지않으면 else문을 돌아서 해당 점검자가 확인해야하는 weak를 check_weak에 넣음

그 check_weak가 오름차순이라면 if문을 그렇지않으면 else문을 돌아서 필요한 이동길이를 length에 넣음

(check_weak[0] == min(check_weak)가 만족하면 오름차순인 이유는 시계방향으로만 이동하기 때문임)

ex) 점검순서 : 1, 5, 6, 10 vs 5, 6, 10, 1

(시계방향으로만 이동하는 이유는 예를들어 [1, 5, 6, 10]에서 시작위치가 1일 때 반시계 방향은 1, 10, 6, 5인데 이때의 이동길이는 시작위치가 5일 때 5, 6, 10, 1의 이동길이와 같기 때문임)

다시 코드로 돌아와서 이어서 다음 for-else문에서 if문에서 length과 같거나 크다면 cd를 해당 점검자로 선택하고 가능한 점검자 리스트인 copy_dist에서 cd를 제거함

모든 for문이 통과한다는 것은 해당 점검이 가능한 점검자가 없다는 것이므로 else문에서 break

첫 for-else문에서 for문으로 id_list를 모두 돌았다는 것은 해당 시작위치들의 점검이 가능하다는 것이므로 else문에서 점검자 수인 d+1을 return함

확인하는 모든 경우의 수가 return d+1을 거치지않게 되면 점검이 불가능하다는 것이므로 마지막에 -1을 return함

 

테스트 결과) - 총합 212.88ms

테스트 1 〉	통과 (0.01ms, 10.2MB)
테스트 2 〉	통과 (0.03ms, 10.2MB)
테스트 3 〉	통과 (4.58ms, 10.2MB)
테스트 4 〉	통과 (2.32ms, 10.3MB)
테스트 5 〉	통과 (1.01ms, 10.1MB)
테스트 6 〉	통과 (9.15ms, 10.4MB)
테스트 7 〉	통과 (0.03ms, 10.3MB)
테스트 8 〉	통과 (0.06ms, 10.1MB)
테스트 9 〉	통과 (0.11ms, 10.2MB)
테스트 10 〉	통과 (17.78ms, 11MB)
테스트 11 〉	통과 (32.18ms, 11.5MB)
테스트 12 〉	통과 (14.01ms, 10.7MB)
테스트 13 〉	통과 (62.73ms, 11.6MB)
테스트 14 〉	통과 (42.44ms, 11.5MB)
테스트 15 〉	통과 (14.67ms, 11MB)
테스트 16 〉	통과 (0.34ms, 10.1MB)
테스트 17 〉	통과 (6.33ms, 10.5MB)
테스트 18 〉	통과 (1.93ms, 10.4MB)
테스트 19 〉	통과 (0.16ms, 10.2MB)
테스트 20 〉	통과 (0.87ms, 10.3MB)
테스트 21 〉	통과 (0.08ms, 10.1MB)
테스트 22 〉	통과 (0.43ms, 10.1MB)
테스트 23 〉	통과 (0.71ms, 10.2MB)
테스트 24 〉	통과 (0.80ms, 10.2MB)
테스트 25 〉	통과 (0.12ms, 10.1MB)