외벽 점검 풀이
코드
from itertools import permutations
def solution(n, weak, dist):
answer = []
dists = [list(x) for x in permutations(dist)]
weaks = [weak] + [weak[i+1:]+[x+n for x in weak[:i+1]] for i, _ in enumerate(weak[:-1])]
for weak in weaks :
for dist in dists :
check = weak[0]
for i, d in enumerate(dist) :
check += d
if check >= weak[-1] :
answer.append(i)
break
else :
check = [x for x in weak if x > check][0]
return min(answer)+1 if answer else -1
이 문제에 관하여
이 문제는 반시계 방향 점검을 고려해줘야합니다.
이 벽에서 4 - 3 - 1 - 10 - 9 순으로 반시계방향 점검과 9 - 10 - 1 - 3 - 4 순으로 시계방향 점검은 같습니다. 따라서 반시계 방향의 점검을 고려해 주기위해 [1, 2, 3, ..., n]의 벽을 [2, 3, 4, ..., n, n+1], [3, 4, 5, ..., n, n+1, n+2]
이런 느낌으로 벽을 늘려준다면 반시계 방향 점검이 해결됩니다. 하지만 벽 전체를 늘려줄 필요없이 weak 배열만 늘려주면 됩니다. 어차피 관심있는건 취약 부분이지 멀쩡한 벽이 아닙니다.
- 반시계방향 점검을 고려하기위해
weak배열을 하나씩 당겨서len(weak)갯수만큼 만들어준다.- 친구들의 점검 순서의 다양성을 위해
dist를permutation으로 섞어준다
이상 주요 알고리즘이었습니다.
solution
weaks = [weak] + [weak[i+1:]+[x+n for x in weak[:i+1]] for i, _ in enumerate(weak[:-1])]
벽을 한칸씩 앞으로 당겨주는 코드입니다. 이코드는
weaks = [weak]
for i, _ in enumerate(weak[:-1]) :
tmp = []
for x in weak[:i+1] :
tmp.append(x+n)
weaks.append(weak[i+1] + tmp)
이 코드를 한줄로 줄인 코드입니다.
이런식으로 동작하는 코드입니다.
그리고 나머지는 반복문을 통해 친구 몇명을 썼고, 그 친구들은 점검을 다 끝마쳤는가?에 대한 처리를 해주어야합니다.
for dist in dists :
check = weak[0]
for i, d in enumerate(dist) :
check += d
if check >= weak[-1] :
answer.append(i)
break
else :
check = [x for x in weak if x > check][0]
for 문은 이런식으로 동작합니다. 천천히 이해하시면 됩니다.
from itertools import permutations
def solution(n, weak, dist):
answer = []
dists = [list(x) for x in permutations(dist)]
weaks = [weak] + [weak[i+1:]+[x+n for x in weak[:i+1]] for i, _ in enumerate(weak[:-1])]
for weak in weaks :
for dist in dists :
check = weak[0]
for i, d in enumerate(dist) : # enum쓴 이유는 dist안에 같은 거리가 있을 수 있기 때문
check += d
if check >= weak[-1] :
answer.append(i)
break
else :
check = [x for x in weak if x > check][0]
return min(answer)+1 if answer else -1
참고로
enum을 쓴 이유는 처음에 제가answer.append(dist.index(d))를 했다가 계속 틀렸습니다. 그 이유는 움짤처럼dist안에 같은 거리를 점검하는 친구들이 있기 때문이었습니다.list.index(i)는 리스트에서i가 가장먼저 나오는 인덱스를 리턴하기 때문에 중복된dist처리를 할 수 없습니다. 따라서enum을 사용해 사용한 친구수를 처리했습니다.