[구현] 외벽 점검

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다.
문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다.

소요시간: 2시간 30분+a

1. 문제 설명

- 원형 건물에 외벽을 보수하려고 할 때, 보수 인원이 가장 적게 드는 경우를 묻는 문제

2. 접근 방식

- 친구 수의 최소값을 리턴해야 한다.
- 어디서 출발해도 상관이 없다.
- 우선 거리가 가장 긴 친구 한 명을 먼저 돌게하자.

- 시계방향으로 도는 것도 가능하고, 반 시계방향으로 도는 것도 가능하기에 index를 통해 돌리면 될 것 같고, index는 길이만큼 나눈 값을 이용해서 초과가 되도 다시 돌 수 있도록 하자.

3. 코드

- 내 코드_Fail

# 시계방향 +1, 반시계방향 -1
import copy

def solution(n, weak, dist):
    friends = sorted(dist, reverse =True)
    weak_ls = [0] * n
    answer = 0
    for i in weak:
        weak_ls[i] = 1
    # 외벽 점검해야 하는 곳은 1로 만든다.
    tmp_ls = [1e9]*n
    for j in friends: # 4 # 길이가 긴 친구먼저 탐색
        answer += 1
        for k in weak: # [1, 5, 6, 10]
            index = k # index의 위치는 바뀐다.
            check_ls = clockwise(n, j, index, weak_ls)
            tmp_ls = check_ls if sum(check_ls) < sum(tmp_ls) else tmp_ls # 만약 합이 작은 애들 중에 거리가 최소인 애들이 존재한다면?
            if sum(tmp_ls) == 0:
                return answer
        weak_ls = tmp_ls
    return -1

def clockwise(n, m, index, weak_ls): # index를 시계방향으로 한 번, 반시계 방향으로 한 번씩 돌린다.
    ls1 = copy.deepcopy(weak_ls)
    ls2 = copy.deepcopy(weak_ls)
    i, j = index, index
    for _ in range(m+1): # 시계방향
        if weak_ls[i] == 1:
            ls1[i] = 0 # 검사한 곳은 0으로
        i += 1
        i %= n
    for _ in range(m+1): # 반시계방향
        if weak_ls[j] == 1:
            ls2[j] = 0
        j -= 1
        j %= n
    result_ls = ls1 if sum(ls1) < sum(ls2) else ls2
    return result_ls

- 해답 코드

from itertools import permutations

def solution(n, weak, dist):
    # 길이를 2배로 늘려서 '원형'을 일자 형태로 표현
    length = len(weak)
    for i in range(length):
        weak.append(weak[i]+n)
    answer = len(dist) + 1 # 친구 수의 최솟값 찾기 위해 '친구수 + 1'로초기화
    # 0부터 lenghth-1까지 위치 각각 시작점으로 설정
    for start in range(length):
        # 친구를 나열하는 모든 경우의 수 확인 최대 8!이면 40,320
        for friends_case in  list(permutations(dist, len(dist))):
            count = 1
            position = weak[start] + friends_case[count-1] # 친구가 커버 가능한 부분
            for index in range(start, start+length):# 처음부터 끝까지 모든 취약점을 확인 (길이만큼만 확인)
                if position < weak[index]: # 점검 위치를 벗어나는 경우
                    count+=1 # 새로운 친구 투입
                    if count > len(dist): # 더 투입이 불가하다면 종료
                        break
                    position = weak[index] + friends_case[count-1]
            print(" ")
            answer = min(answer, count) # 최소값 계산
    if answer > len(dist):
        return -1
    return answer

4. 코멘트

- 원형으로 나열된 데이터를 처리하기 위해 길이를 2배로 늘려서 '원형'을 일자 형태로 만드는 작업을 했다.

- '순열' 라이브러리를 활용해서 친구를 나열하는 모든 경우를 구하고, 이를 이용해 완전탐색을 실시했다.

- 히든 테스트 케이스 중 13개 가량이 계속 안돼서 2시간 가량 고민을 하다가 결국 해답을 봤는데, 앞 문제와 비슷하게 '순열'을 사용해서 문제를 풀었다.

- 근데, 만약 순열로 문제를 풀어야 한다는 것을 알고 있었더라도, 원형 데이터를 처리하기 위한 방법이나 아니면 완전탐색을 해서 탐색하는 방법 등을 생각하지 못했을 거 같다.

- 구현 문제를 풀다가 해답을 보면 '너는 왜케 쪼잔하게 코드를 짜냐?' 라고 말을 하는 것 같은 느낌을 받는다...