외벽점검
2020 KAKAO BLIND RECRUITMENT🤎
문제링크 https://programmers.co.kr/learn/courses/30/lessons/60062
문제풀이
이 문제의 풀이는 완전탐색으로 진행하였다.
python 의 itertools 라이브러리를 사용해서 dist 배열의 모든 경우를 다 permutations으로 구했다. 문제 풀이의 순서는 다음과 같다.
- dist의 모든 경우의 수 구하기 (dists)
- weak의 시작 지점이 다른 모든 경우 test_weak로 만들기.
- for 문을 통해 각 index를 돌면서 0번째 부터 시작하는 weak, 1번째 부터 시작하는 weak.. 로 만들기
- visited 배열을 만들기
- n 의 개수만큼 배열을 만들고 모두 1 값으로 초기화하기
- weak에 있는 지점들은 0으로 초기화하기 (아직 방문 못한곳)
- 차후 visited의 모든 값이 1일 경우 모든 지점을 방문한 것으로 처리
- dist의 모든 경우 하나씩 돌면서 test_weak도 같이 for 문으로 돌기
- 아직 방문안한곳만 연산
- dist의 d 값과 test_weak의 t 값이 n을 넘어갈 경우 0인덱스로 돌아가서 그만큼 다시 더해주기
- t 부터 t+d 값 만큼 visited 1로 초기화하기
- break
- 방문한곳은 pass 하고 다음 for문
- 아직 방문안한곳만 연산
- visited 값이 모두 1인 경우 (flag = 1) 현재의 answer 값과 비교해서 더 작은 cnt면 answer에 할당하기
answer == float('inf)answer 값이 아예 변화가 없다면 -1 return
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
from itertools import permutations
def solution(n, weak, dist):
answer = float('inf')
dists = list(permutations(dist))
for dist in dists:
for w in range(len(weak)):
test_weak = weak[w:]+weak[:w]
visited = [1]*n
for i in test_weak:
visited[i] = 0
cnt = 0
flag = 0
for d in dist:
for t in test_weak:
if visited[t] == 0:
x = d + t
if x >= n:
x %= n
visited[t:] = [1]*(n-t)
visited[:x+1] = [1]*(x+1)
else:
visited[t:x+1] = [1] *(x-t+1)
cnt += 1
if visited == [1]*n:
flag = 1
break
if flag == 1:
break
if flag == 1 and cnt < answer:
answer = cnt
if answer == float('inf'):
return -1
else:
return answer