외벽 점검

문제

---

https://programmers.co.kr/learn/courses/30/lessons/60062

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

 

 

나의 풀이

---

브루트 포스 문제이다. 생각보다 어려웠던 것 같다. 중요하게 고려해야 할 것은 크게 두 가지이다.

1. 외벽은 원형으로 이루어져 있는데 주어진 weak 리스트가 그것을 반영하지 못한다. -> weak 리스트 배열의 길이를 2배로 늘려서 해결. 예컨대, weak = [1,5,6,10], n=12라면 weak_point = [1,5,6,10,13,17,18,22]로 해서 이 중에서 원래 weak의 원소 갯수였던 4개의 연속된 지점을 선택하는 문제로 바꿀 수 있다.

2. 같은 상황이라도 dist 배열의 친구들을 어떠한 위치에 어떠한 순서로 넣을지에 따라 결과가 달라진다. -> 순열 사용

 

 

코드

---

from itertools import permutations

def solution(n, weak, dist):
    INF = 987654321
    answer = INF
    weak_point = weak + [ w + n for w in weak ]
    L = len(weak) 
    # 시작점
    for (idx, start) in enumerate(weak):
        # 가능한 모든 케이스의 순열
        for p in permutations(dist):
            count = 1
            pos = start
            for d in p:
                pos += d
                if pos >= weak_point[idx + L - 1]:
                    answer = min(answer, count)
                    break
                else:
                    pos = [w for w in weak_point if w > pos][0]
                    count += 1
    return -1 if answer == INF else answer