Programmers - 외벽 점검

문제 링크

가능한 모든 상황을 시뮬레이션하는 문제이다.
처음에는 1명부터 len(dist)명 까지 순차적으로 탐색했는데,
시간초과가 발생하여 이분탐색으로 변경하니까 통과했다.

함수 설명
  1) move(): dist에서 차례대로 weak 방문했을 때 전부 점검 가능한지를 확인하는 로직
  2) simulation(): 모든 가능한 상황들을 시뮬레이션
    - 모든 dist 순서, 모든 weak 순서를 전부 테스트

from collections import deque
from itertools import permutations


def solution(n, weak, dist):
    dist = sorted(dist, reverse=True)

    # 이분탐색으로 변경
    l = 1
    r = len(dist)
    answer = -1
    while l <= r:
        mid = (l+r)//2
        if simulation(n, dist[:mid], weak):
            answer = mid
            r = mid - 1
        else:
            l = mid + 1

    return answer


# 모든 dist 순서에서 move
def simulation(n, sub_dist, weak):
    rotated_weak = deque(weak)
    for seq in permutations(sub_dist):
        for i in range(len(weak)-1):
            if move(seq, rotated_weak):
                return True
            # rotate
            first = rotated_weak.popleft()
            rotated_weak.append(first + n)

    return False
    
# dist에서 차례대로 weak 방문 했을 때 전부 점검 가능한지 여부
def move(dist, weak):
    i = 0
    end = weak[0] + dist[i]
    for w in weak:
        if w > end:
            i += 1
            if i >= len(dist):
                return False
            end = w+dist[i]
    return True