문제

2020년 카카오 신입 공채 코딩테스트 문제
문제 이름 : 외벽점검

해결 방법

무지무지 어려웠다. 처음에는 그리디로 dist리스트에서 가장 큰녀석들 부터 점검을 하면서 시계방향 반시계방향으로 돌면 충분히 해결 할 수 있을줄 알았지만, 그렇게 쉽지 않았다 원형 레스토랑에서 시작지점이 자유로웠기에
for문만으로 해결하기는 매우 어려웠다.
따라서 핵심 방법은 몇가지 있었다.

1. weak를 2배로 길이를 늘려 원형을 도는 것의 구현이 용이했다.
   예를 들자면 ...

원래 weak가 [1, 3, 5, 10]이고 n이 12일때
weak를 [1,3, 5, 10, 13, 15, 17, 22]로 확장했고
반시계 방향인 Oweak도 만들어주었다.
[2, 7, 9 ,11, 13, 19, 21, 23] 이런식으로

2. 모든 친구순서를 추출해내서 시작점은 결국 len(weak)(최대 15개)이므로 15경우의 시작지점 X factorial(8)정도의 수준의 시간 복잡도가 나왔다

3. 세번째는 그냥 구현 기술 이다 시계방향으로 돌았을 때 몇개를 방문하고 이걸 기록하고 그때 몇명의 친구를 사용했는지 이 세번째 방법은 단순이 스킬이 아니라 체화되어있는 구현실력 그자체였다.

이 3가지 를 잘 결합 하면 다음의 코드가 자연스럽게 나왔다.

해답 코드

from itertools import permutations

def solution(n, weak, dist):
    answer = 16
    weak_size = len(weak)
    dist_size = len(dist)
    #반시계 weak배열 만들기
    Oweak = []
    for i in range(weak_size-1, -1, -1):
        Oweak.append(n-weak[i])
    #weak배열 Oweak배열 확장
    for i in range(weak_size):
        weak.append(n+weak[i])
        Oweak.append(n+weak[i])
    #무작위로 친구순서 뽑아내서 최솟값 추출해내기
    for friends in permutations(dist, dist_size):
        #시작지점 순서대로해서 해보기
        for s in range(weak_size):
            #방문한 weak개수
            visit = 0
            #친구 순서대로 시계방향으로 돌아주기
            count = 0
            for friend in friends:
                count += 1
                #현재 순서의 친구가 이동할수 있는거리로 최대한 방문
                destination = weak[s+visit] + friend
                for i in range(s+visit, s+weak_size+1):
                    if destination >= weak[i]:
                        visit += 1
                        if visit >= weak_size:
                            break
                #만약 다 방문 했다면
                if visit >= weak_size:
                    answer = min(answer, count)
                    break
            #방문한 weak개수
            visit = 0
            #친구 순서대로 반시계방향으로 돌아주기
            count = 0
            destination = weak[s+visit] + friend
            for friend in friends:
                count +=1
                position = Oweak[s+visit]
                #현재 순서의 친구가 이동할수 있는거리로 최대한 방문
                for i in range(s+visit, s+weak_size+1):
                    if destination >= Oweak[i]:
                        visit += 1
                        if visit >= weak_size:
                            break
                #만약 다 방문 했다면
                if visit >= weak_size:
                    answer = min(answer, count)
                    break
                else:
                    position = weak[s+visit]
                
    if answer >= 16:
        return -1
    return answer

이 문제에서 배운점

시간이 충분하다면.....

permuation함수나 combination함수를 통해서 완전 탐색도 해볼만한
방법이다.