(Python) [2020카카오공채] 외벽 점검

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

코딩테스트 연습 - 외벽 점검 | 프로그래머스

 

1. 제한사항

• 1 <= n <= 200, n은 자연수
• weak의 길이 : 1이상 15이하
  • 서로 다른 두 취약점의 위치가 같은 경우는 주어지지 않는다.
  • 취약 지점의 위치는 오름차순으로 정렬되어 주어진다.
  • weak의 원소는 0이상 n-1이하인 정수
• dist의 길이 : 1이상 8이하
  • dist의 원소는 1이상 100이하인 자연수
• 친구들을 모두 투입했음에도 취약 지점을 전부 점검할 수 없는 경우, return -1

 

2. 입출력 예

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

 

3. 문제풀이

• 원형을 하나의 직선으로 표현하고자 했고, 위치를 왼쪽으로 한칸씩 옮겨주는 과정을 넣어주고 싶어서 deque 객체를 사용했다. (시간을 단축시키기 위해서)
• 순열 - 선택한 친구를 순서대로 배치해주기 때문에 순열 개념을 사용했다.(모든 친구를 투입해도 외벽점검을 못할 경우 어쩔수 없지만, 그 외의 경우에는 dfs를 사용하는 것 보다 순열을 이용한 반복문이 더 빠르다.)

---

[2020 카카오 공채] 외벽 점검¶

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

---

In [1]:

from collections import deque 
import itertools ## 순열이용

In [2]:

## 친구를 투입하고나서, 그 다음 친구를 투입할때
def next_index(queue, d, start_index=0):
    start_num = queue[start_index]
    for i in range(1, d+1):
        try:
            if queue[start_index + 1] == start_num + i:
                start_index = start_index + 1
        except:
            break
    return start_index+1

In [3]:

def solution(n, weak, dist):
    dist.sort(reverse=True)
    weak = deque(weak)
    for i in range(1,len(dist)+1):
        ## i:투입할 친구 수와 관련이 있다.
        ## 1명만 투입했을 때
        if i==1:
            for _ in range(len(weak)):
                d = dist[0]
                if weak[-1] <= weak[0] + d:
                    return 1
                else:
                    weak.rotate(-1)
                    weak[-1] = weak[-1] + n
            ## weak 원상복구
            weak = deque(map(lambda x:x%n, weak))
        else:
            dist_2 = list(itertools.permutations(dist[:i]))
            for select_set in dist_2:
                for _ in range(len(weak)):
                    start_index = 0
                    for d in select_set:
                        ## 다음번 친구가 투입될 위치 : start_index
                        start_index = next_index(weak, d, start_index)
                        if start_index == len(weak):
                            return i
                    weak.rotate(-1)
                    weak[-1] = weak[-1] + n
                ## weak 원상복구
                weak = deque(map(lambda x:x%n, weak))
    return -1

In [4]:

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

In [5]:

solution(n, weak, dist)

Out[5]:

2