출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

핵심 개념

Complete search
greedy
manage circular case
permutations

변수

(1) 몇 명의 친구를 고르는지
(2) 어떤 값을 가진 친구들을 고르는 지
(3) 고른 친구들은 어떤 순서로 진행하는 지
(4) 친구는 각각 어떤 weak 지점부터 시작해야 하는지
(5) 친구는 각각 어떤 방향<시계방향, 반시계> 으로 진행해야하는지

풀이법

일단 전체적으로는 Complete Search 문제 입니다.
dict와 weak 길이가 충분히 작기 때문에 완전 탐색방법도 Reasonable 하다고 볼 수 있고
모든 변수가 독립적으로 결과에 영향을 끼치기 때문에, 최악의 경우 모든 경우의 수를 구해서 대조를 해봐야 합니다.

중복을 최대한 없애고, Greedy한 접근으로 경우의 수 가지치기 하기
최악의 경우 모든 경우의 수를 봐야하지만, 우리는 고른 인원의 최솟값만 구하면 되고(greedy)
전체적으로 weak가 circular case 라는 것을 집중하면 상당 수의 중복 되는 경우의 수를 가지치기 할 수 있습니다.

먼저, greedy로 가지치기 할 수 있는 부분은 변수 (1)과 (2)입니다.
(1)은 outer-loop로 두고 i를 1부터 시작해서, 조건을 만족하는 할 때, 바로 return하게 합니다.
(2)은 처음부터 dict를 내림차순으로 지정하여 가장 멀리 갈 수 있는 친구부터 배정합니다.

두 번째, 전체적으로 weak는 둘레가 n인 circular 구조 위에 있습니다.
이것을 이용해, (4)과 (5)을 한꺼번에 고려할 수 있습니다.
차례대로 시작 부분을 하나 지정하고, 그 시작을 기준으로 왼쪽과 오른쪽 파트로 나누어서
왼쪽파트는 n값을 플러스 하면 됩니다.
Ex) n= 12일떄, [1,5,6,10] -> 5선택 -> [5, 6, 10, 13] , [1,5,6,10] -> 6선택 -> [6, 10, 13, 17]

위의 예처럼 하면 시작지점과 진행방향을 모두 커버할 수 있고
(혹시 의심가시면 종이에 몇 가지 예 적어보시면 같은 결과가 나옵니다.)
이것은 circular 구조를 고려하지 않아서 모든 weak에 2가지 방향성을 주는 경우에 비해
비교 해야할 경우의 수 숫자가 2**n -> n으로 줄어들게 됩니다.

마지막으로 변수 (3)은 어떠한 방식으로도 가지치기를 할 수 없어서
itertools에서 사용하시거나, user-defined로 permutation를 구현하셔서
완전탐색을 끝내시면 될 거 같습니다.

구현 by Python

import sys
import os

def permutation(candidates, Prepermuation, res):
    if len(candidates) == 0: res.append(Prepermuation); return
    else:
        for i in range(len(candidates)):
            permutation(candidates[:i]+candidates[i+1:], Prepermuation + [ candidates[i] ], res)
        return

def solution(n, weak, dist):
    # complete search
    dist.sort(reverse = True)

    for i in range(1, len(dist)+1):
        permutations = []; permutation(dist[:i], [], permutations)
        for p in permutations:
            for start in range(len(weak)):
                _left = weak[:start]; _right = weak[start:]
                traverse_list = _right + [x+n for x in _left]; candidate = p.copy()
                while traverse_list and candidate:
                    cur = traverse_list.pop(0); d = candidate.pop(0);
                    Cover = cur + d
                    while traverse_list and traverse_list[0] <= Cover: traverse_list.pop(0)

                if not traverse_list:
                    return i
    return -1