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

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

코딩테스트 연습 - 외벽 점검

 

풀면서 while, for 가 많이 나와서 복잡하기도 하고, 이렇게 푸는 게 아닌가 싶기도 하여 다른 방법을 생각해보려고 하였으나 배열의 길이도 짧고 해서 한 번 시도해봤다. 다행히 통과되었다.

 

접근 방법은 [1, 5, 6, 10] -> [1, 5, 6, 10, 1+12, 5+12, 6+12, 10+12] 설정하여 반시계방향은 +12 해서 한 방향으로만 생각하도록 하였다. (가능한 역방향의 마지막은 10 ~ 6+12 이기 때문에 마지막 원소인 10+12 는 없어도 된다.)

 

특정 경우에는 예를 들어, 투입 순서가 4 -> 3 -> 2 보다 4 -> 2 -> 3 이보다 많은 처리를 할 수가 있으므로 순열을 사용한다. 하지만, 4 -> 3 -> 1 이 되는 것을 4 -> 3 -> 2 가 처리를 못 하는 경우는 없다. 같은 우선순위에는 더 큰 수가 제일 취약점을 처리하는 수가 같거나 많다.

 

그러므로 dist 를 오름차순으로 sort() 하여 가장 큰 원소를 array 라는 배열에 담고 array 의 길이에 대해 순열을 구하여 모든 취약점이 처리될 때 바로 array 의 길이를 return 하면 된다. 모든 취약점이 처리되지 않으면 array 에 다음으로 가장 큰 원소를 array 에 담고 위의 과정을 반복한다. 모든 과정을 수행하여도 처리되지 않으면 -1 을 return 한다.

 

from itertools import permutations as P
from collections import deque

def solution(n, weak, dist):
    answer = -1
    N = len(weak)
    weak.extend(list(map(lambda x : x + n, weak)))
    dist.sort()
    array = [] 
    
    while dist: 
        array.append(dist.pop())
        p_array = list(P(array))
        
        for i in p_array:
            for j in range(N):
                queue = deque(list(i))
                value = weak[j] + queue.popleft()
            
                for k in range(1, N):
                    if value < weak[j+k]:
                        value = weak[j+k]
                        if queue:
                            value = value + queue.popleft()
                        else:
                            break
                
                    if k == N - 1:
                        if value >= weak[j+k]:
                            return len(array)
                                                    
    return answer

print(solution(12, [1, 5, 6, 10], [1, 2, 3, 4])) # 2