[프로그래머스] 외벽 점검 파이썬

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/60062

코딩테스트 연습 - 외벽 점검

 

그리디하게 dist를 정렬해서 가장 긴 것 부터 풀면 되지 않을까 했다가 계속 틀렸던 문제이다.

 

weak = [0,10,30,50,100,120]

dist = [5,10,50,100]

이 경우 답은 1이다

weak가 100인 점에서 길이가 100인 친구가 돌면 된다.

 

그래서 브루트포스로 해결하였다.

dist의 순서를 섞고 0번째부터 그 순서대로 다 돌려보면서 가장 작은 것을 찾도록 했다.

dist 순서대로 weak의 첫번째 부터 시계방향으로 확인하는데 dist의 값 이내에 weak인 구역의 개수를 세고, 최대 길이이거나 이미 탐색한 구역이라면 그 지점부터 dist로 확인하였다.

dist 순서대로 진행하다가 남은 weak가 없다면 그때의 개수를 정답과 체크해서 해결했다.

 

from itertools import permutations
INF = 9876543210

def solution(input_n, input_weak, input_dist):
    global answer, dist, weak, n, m
    n = input_n
    weak = input_weak
    dist = input_dist
    m = len(weak)

    answer = INF
    remain = len(weak)

    for order in permutations(dist,len(dist)):
        for start in range(m):
            visited = [False]*n
            check_weak(start, 0, order, visited, 0, remain)
    return answer if answer != INF else -1


def check_weak(start, now, order, visited, ans, remain):
    global answer
    if ans >= answer:
        return
    
    if remain == 0:
        answer = min(answer, ans)
        return

    if now == len(order):
        return

    w = weak[start]
    visited[w] = True
    cnt = 1
    end = start
    for _ in range(m):
        end = (end+1)%m
        if not is_possible(w,weak[end],order[now]) or visited[weak[end]]:
            break
        else:
            visited[weak[end]] = True
            cnt += 1
    check_weak(end,now+1,order,visited,ans+1,remain-cnt)
    
def is_possible(start,end,max_dist):
    if end - start < 0:
        if n - start + end <= max_dist:
            return True
        else:
            return False
    else:
        if end - start <= max_dist:
            return True
        else:
            return False