문제
나의 풀이
: 힌트 봐야겠다..
- 아이디어가 도저히 안 떠올라서, 구글링을 하여 3가지 힌트를 얻었다.
- weak과 dist의 길이가 엄청 짧음 -> 완전탐색
- 원형 데이터 -> 길이를 2배로 늘린 일자 형태로 변환
- dist가 최대 8 -> 순열로 모든 경우의 수 확인하기
이제 혼자 풀어봐야지..
-> 하다가 막혀서 책 답지보고 틀 잡기
-> 또 막혀서 다시 답지보고 따라하기
-> 다시 풀어보자!
1. why 실패?
from itertools import permutations
def solution(n, weak, dist):
len_weak, answer = len(weak), len(dist) + 1
for i in range(len_weak): # weak의 길이를 2배로 늘림
weak.append(weak[i] + n)
for start in weak: # 취약 지점에서 출발
for friends in list(permutations(dist, len(dist))): # 경우의 수 각각에 대하여
count = 1 # 점검 인원 1명으로 시작
arrival = start + friends[count - 1] # 도착 지점: 출발 지점 + 친구가 가능한 최대 거리
for point in weak: # 출발 지점에서부터 하나씩 모든 지점을 살펴보며
if arrival < point: # 최대 가능 거리를 갔음에도 여전히 점검할 지점이 남아있는 경우
count += 1 # 친구 1명 더 투입
if count > len(dist): # 더이상 투입할 친구가 없는 경우, break
break
arrival = point + friends[count - 1] # 새로운 친구의 도착 지점 갱신
answer = min(answer, count) # 경우의 수를 살펴보면서, 더 적은 인원으로 갱신
if answer > len(dist): # 필요한 친구 수가 주어진 친구 수보다 많을 경우, -1 반환
return -1
return answer: weak의 원래 길이만큼만 돌아야하는데, for문 범위를 weak으로 하면 2배 늘어진 weak을 돌기 때문에 실패!
2. 성공..but.. 다시 풀자
from itertools import permutations
def solution(n, weak, dist):
len_weak, answer = len(weak), len(dist) + 1
for i in range(len_weak): # weak의 길이를 2배로 늘림
weak.append(weak[i] + n)
for start in range(len_weak): # 취약 지점에서 출발
for friends in list(permutations(dist, len(dist))): # 경우의 수 각각에 대하여
count = 1 # 점검 인원 1명으로 시작
arrival = weak[start] + friends[count - 1] # 도착 지점: 출발 지점 + 친구가 가능한 최대 거리
for point in range(start, start + len_weak): # 출발 지점에서부터 하나씩 모든 지점을 살펴보며
if arrival < weak[point]: # 최대 가능 거리를 갔음에도 여전히 점검할 지점이 남아있는 경우
count += 1 # 친구 1명 더 투입
if count > len(dist): # 더이상 투입할 친구가 없는 경우, break
break
arrival = weak[point] + friends[count - 1] # 새로운 친구의 도착 지점 갱신
answer = min(answer, count) # 경우의 수를 살펴보면서, 더 적은 인원으로 갱신
if answer > len(dist): # 필요한 친구 수가 주어진 친구 수보다 많을 경우, -1 반환
return -1
return answer다른 사람 풀이
1. 프로그래머스
from collections import deque
def solution(n, weak, dist):
dist.sort(reverse=True)
q = deque([weak])
visited = set()
visited.add(tuple(weak))
for i in range(len(dist)):
d = dist[i]
for _ in range(len(q)):
current = q.popleft()
for p in current:
l = p
r = (p + d) % n
if l < r:
temp = tuple(filter(lambda x: x < l or x > r, current))
else:
temp = tuple(filter(lambda x: x < l and x > r, current))
if len(temp) == 0:
return (i + 1)
elif temp not in visited:
visited.add(temp)
q.append(list(temp))
return -1: 덱을 이용해서도 풀 수 있구나..?! 찬찬히 뜯어봐야겠다ㅠ
2. set으로도 풀 수 있구나?!
def solution(n, weak, dist):
W, F = len(weak), len(dist)
repair_lst = [()] # 현재까지 고칠 수 있는 취약점들 저장 (1,2,3)
count = 0 # 투입친구 수
dist.sort(reverse=True) # 움직일 수 있는 거리가 큰 친구 순서대로
# 고칠 수 있는 것들 리스트 작성
for can_move in dist:
repairs = [] # 친구 별 고칠 수 있는 취약점들 저장
count += 1
# 수리 가능한 지점 찾기
for i, wp in enumerate(weak):
start = wp # 각 위크포인트부터 시작
ends = weak[i:] + [n+w for w in weak[:i]] # 시작점 기준 끝 포인트 값 저장
can = [end % n for end in ends if end -
start <= can_move] # 가능한 지점 저장
repairs.append(set(can))
# 수리 가능한 경우 탐색
cand = set()
for r in repairs: # 새친구의 수리가능 지점
for x in repair_lst: # 기존 수리가능 지점
new = r | set(x) # 새로운 수리가능 지점
if len(new) == W: # 모두 수리가능 한 경우 친구 수 리턴
return count
cand.add(tuple(new))
repair_lst = cand
return -1: dist가 큰 친구부터 차례로 위치 시킴 set 이용하여 모든 취약 지점이 수리 되었는지 확인
- 집합에 집합을 넣을 수 없으므로 tuple로 변경해서 넣음
- 초기화를 set이 아닌 repair_lst = [()] 로 하는 이유는 for x in repair_lst: # 기존 수리가능 지점 new = r | set(x) 부분에서 처음에 스킵되지 않고 공집합과의 합집합된 것이 적용되어야 하기 때문
내 인생의 주연