외벽 점검

INGBEEN·2021년 11월 8일

알고리즘 문제

목록 보기

15/20

문제 설명

https://programmers.co.kr/learn/courses/30/lessons/60062
<입력>
<출력>
<예시>

나의 풀이 -> 실패

아무리 생각해도 경우의 수가 너무 많다. 
하나하나 if else로 할 수 없다. 
답이 나오지 않아 답을 보았다.....

책 풀이

1 . 원순열을 일자로 표현하기 위해 주어진 리스트를 2배로 늘린다.

2 . 그 후 0부터 lenght - 1 까지의 위치를 각각 시작점으로 설정한 다음, 친구를 나열하는 모든 경우의 수 각각에 대하여 확인한다.

2-2 . 친구를 하나씩 투입하면서 그 친구가 점검할 수 있는 마지막 위치를 계산한 다음 다음 친구를 투입해 반복한다.

2-3 . 점검할 수 있는 위치를 벗어나는 경우 break, 아니면 answer = min(answer, 투입한 친구 수) # answer은 처음에 큰 수로 초기화한다.

3 . answer이 아직도 큰 수라면 -1, 아니면 answer 반환

from itertools import permutations

def solution(n, weak, dist):
    length = len(weak)
    for i in range(length):
        weak.append(weak[i] + n)
    answer = len(dist) + 1
    for start in range(length):
        for friends in list(permutations(dist, len(dist))):
            count = 1 
            position = weak[start] + friends[count - 1]
            for index in range(start, start + length):
                if position < weak[index]:
                    count += 1
                    if count > len(dist):
                        break
                    position = weak[index] + friends[count - 1]
            answer = min(answer, count)
    if answer > len(dist):
        return -1
    return answer

출처 : https://github.com/ndb796/python-for-coding-test/blob/master/12/8.py

다른 사람 풀이

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