Q14. 외벽 점검
🐣문제
레스토랑의 구조는 완전히 동그란 모양이고 외벽의 총 둘레는 n미터이며, 외벽의 몇몇 지점은 추위가 심할 경우 손상될 수도 있는 취약한 지점들이 있습니다.
따라서 주기적으로 친구들을 보내서 점검을 하는데, 점검 시간을 1시간으로 제한했습니다.
친구들이 1시간 동안 이동할 수 있는 거리는 제각각이기 때문에, 최소한의 친구들을 투입해 취약 지점을 점검 하려고 합니다. 편의 상 레스토랑의 정북 방향 지점을 0으로 나타내며, 취약 지점의 위치는 정북 방향 지점으로부터 시계 방향으로 떨어진 거리로 나타냅니다. 또, 친구들은 출발 지점부터 시계, 혹은 반시계 방향으로 외벽을 따라서만 이동합니다.
외벽의 길이 n, 취약 지점의 위치가 담긴 배열 weak, 각 친구가 1시간 동안 이동할 수 있는 거리가 담긴 배열 dist가 매개변수로 주어질 때, 취약 지점을 점검하기 위해 보내야 하는 친구 수의 최소값을 return 하도록 solution 함수를 완성해주세요.
프로그래머스 링크 | https://programmers.co.kr/learn/courses/30/lessons/60062
🐥풀이
원형 모양이므로 주어진 취약점 리스트를 2배로 늘린다. (예를 들어 길이가 12인 원형 모양에 취약점 위치는 [1, 5, 6, 10] 이면 [1, 5, 6, 10, 1+12, 5+12, 6+12, 10+12]로 늘리는 것이다.) 원형이기 때문에 n을 더해주고, 시계방향과 반시계방향으로 모두 이동 가능하므로 리스트를 2배로 늘려야 한다.
이제 친구 투입을 해야하는데, 투입 순서에 따라서도 필요한 친구 수가 달라진다. 따라서 친구가 투입되는 순서의 모든 경우를 판단하여 필요한 친구 수를 구해야 한다.
한 투입 케이스에서, 친구를 1명씩 투입시켜며 필요한 친구 수를 판단한다. 친구 1명을 투입하고, 이동 가능 거리를 구한다. 점검 시작점은 정해지지 않았으므로 취약점을 시작점으로 잡는 것이 유리하다. 따라서 이동 가능 거리는 '(취약점의 위치)+(친구의 이동 가능 거리)'가 된다.
이동 가능 거리를 구했으면, 취약점 위치를 하나씩 판단한다. (취약점 위치) > (이동 가능 거리)가 되면 현재 친구 수로 점검할 수 없으므로 새로운 친구를 투입한다. (단, 더 이상 친구를 투입할 수 없는 경우가 되면 점검 불가하므로 멈추고 다음 투입 케이스로 넘어간다.) 친구 투입 후 이동 가능 거리를 업데이트 한다. ((새로운 이동 가능 거리) = (취약점의 위치) + (투입된 친구의 이동 가능 거리))
모든 취약점 위치를 점검했으면 현재 친구 수를 answer 변수에 저장한다. (단, answer < (현재 친구 수)이면 저장하지 않는다. answer = min(현재 친구 수, answer)이다.)
모든 투입 케이스를 돌았으면, 친구 수의 최솟값인 answer이 가능한 친구 수(len(dist))를 넘지 않으면 answer을 반환한다. 단, 가능한 친구 수를 넘으면 점검이 불가하므로 -1을 반환한다.
🐓코드
from itertools import permutations
def solution(n, weak, dist):
wl = len(weak) # 점검 지점 수
# 점검 지점 2배로 늘리기 (원형)
for i in range(wl):
weak.append(weak[i]+n)
answer = len(dist)+1 # 친구 수 + 실패 케이스
for i in range(wl):
check = [weak[j] for j in range(i,i+wl)] # 외벽 돌기 케이스
friends = list(map(list, permutations(dist, len(dist)))) # 친구 투입 케이스
for friend in friends:
cnt = 1
distance = check[0]+friend[cnt-1] # 점검 가능 거리(시작점+이동거리)
for j in range(wl):
if check[j]>distance: # 점검 불가
cnt += 1 # 친구 투입
if cnt>len(dist): # 친구 부족
break
distance = check[j]+friend[cnt-1] # 이동거리 업데이트 (다음 친구)
answer = min(answer, cnt)
if answer>len(dist):
return -1
return answer⭐2022.04.08
원형 모양인 것부터 너무 어려웠다 엉엉!! 결국 구글링으로 풀이방법 알아내서 풀어버렸어 ㅠ.ㅠ 카카오.. 어렵다..
