23.03.14 파이썬 코딩 퀴즈#196 외벽 점검 (프로그래머스 스쿨)

이번 문제는 외벽 점검 문제이다.

설명에서 부터 냄새가 나는게, 역시나 카카오 블라인드 공채 문제이다.

레스토랑의 구조는 원형이고, 외벽의 총 둘레는 n 미터이다. 외벽의 몇몇 지점은 취약지점으로 설정된다.

친구들이 1시간 동안 이동 가능한 거리는 dist 배열로 전달된다.

편의상 레스토랑의 정북 방향 지점은 0으로 나타내며, 취약 지점의 위치는 시계 방향으로 떨어진 거리를 의미한다. 그리고 친구들은 출발 지점으로부터 시계, 혹은 반시계 방향으로 외벽을 따라서 이동 가능하다.

즉 이게 무슨 말인지 다시 한번 생각해봐야 한다.

n 이 12가 주어졌다면 원의 둘레는 12 가 된다. 그리고 [1,5,6,10]이 취약 지점으로 주어지고, 이는 시계를 생각하면 1시, 5시, 6시, 10시 가 된다. 그리고 dist 로는 [1,2,3,4] 가 주어졌다.

이를 그림으로 표현하면 위와 같은 형태이다.

친구들의 출발 지점은 어느방향에서나 가능하다. 

따라서 10m 지점에서 이동거리가 4m인 친구를 투입시켜 1m 지점까지 순찰이 가능하다.

그리고 남은 5m, 6m 지점은 다른 친구 한명만 투입하여도 순찰이 가능하다 따라서 이 때, 필요한 친구의 수는 2명이다.

 

입출력 예 2 를 그림으로 표현하면 위와 같다.

이동거리가 7m 인 친구를 4m 에서 출발시켜 반시계 방향으로 순찰을 돌리면 정확히 9m 에서 순찰이 완료된다.

따라서 이 경우에는 1명의 친구만 필요하다.

만약 모든 친구들을 투입하여도 모든 취약지역 순찰을 완료할 수 없다면 -1를 반환하면 된다.

 

이 문제에서 가장 먼저 생각해야할 부분은 무엇일까? 바로 지점간의 거리이다.

즉 특정 지점을 출발점으로 설정한 뒤, 그 지점으로부터 시계 방향으로 진행했을때의 최소 거리가 되는 지점을 탐색의 시작점으로 설정하고 시작하면 될것 같다.

그 이유는 입출력 예 2에서 4를 기준으로 역방향 탐색하면 9까지 진행하게 되고, 9를 기준기준으로 정방향 탐색하면 4까지 진행하기 때문이다. 즉 양쪽 방향을 신경쓸 필요가 없다. 

그리고 가장 효율을 따지는 문제이므로, 순찰 시간이 가장 긴 친구가 가장 긴 구간을 돌게 해주면 된다. 

 

이제 코드를 살펴보자. 먼저 순열을 만들어주기 위해 itertools 를 사용하였다.

answer 은 최대값으로 시작하기 때문에 모든 친구가 순찰에 동원되는 len(dist)로 사용하여도 무방하다.

한가지 예외처리는 dist의 최대값이 n 이상이라면, 이 경우 1명의 친구가 모든 구역을 순찰할 수 있다.

우선 해야할 작업은 배열의 연장이다. 구해둔 lenw 를 이용해서 weak[w]값이 n 만큼 증가시켜 weak 에 다시 넣어주자.

그리고 이제 반복문을 돌아주게 된다

start_p는 weak를 탐색할 index 값이다. 즉 start_p에서 start_p+len(weak) 한 값은 언제나 weak 안에 존재하고, 처음 전달받은 weak 값의 갯수만큼 탐색 가능하다.

comb 는 dist 배열의 요소를 len(dist) 만큼 뽑아서 만든 순열이다.

그리고 cnt = 1 에서 시작한다. cnt 는 순찰에 동원된 친구의 수를 기록한다

position 은 현재 지점에서 comb[0]을 더한 값으로 첫번째 순찰자가 이동 가능한 거리를 나타낸다.

그리고 이제 start_p부터 start_p+len(weak) 만큼을 돌게 된다.

즉 n 이 10 이고, weak 가 [1,5,7,9] 라면 확장된 weak는 [1,5,7,9,11,15,17,19] 이고 permutations()에 의해 생성된 첫번째 순찰자가 4 라면 순찰자가 처음 순찰가능한 거리 position 은 weak[0]+4 = 5가 된다. 따라서 i가 3이 된 시점에서 새로운 순찰자가 한명 추가가 된다. 그리고 순찰자 수를 비교하여 len(dist)를 초과하였다면 position 을 갱신하지 않고 종료한다.

그리고 answer 과 cnt 중 최소값을 answer로 갱신하며 다음 comb 로 이동한다.

 

위 코드의 핵심은 배열의 확장과 순열의 조합에 있다. 물론 다른 방법으로도 얼마든지 풀이가 가능하다.