[이코테/구현/카카오 기출] 외벽 점검 (정답, 풀이)

문제

레스토랑을 운영하고 있는 "스카피"는 레스토랑 내부가 너무 낡아 친구들과 함께 직접 리모델링 하기로 했습니다. 레스토랑이 있는 곳은 스노우타운으로 매우 추운 지역이어서 내부 공사를 하는 도중에 주기적으로 외벽의 상태를 점검해야 할 필요가 있습니다.
레스토랑의 구조는 완전히 동그란 모양이고 외벽의 총 둘레는 n미터이며, 외벽의 몇몇 지점은 추위가 심할 경우 손상될 수도 있는 취약한 지점들이 있습니다. 따라서 내부 공사 도중에도 외벽의 취약 지점들이 손상되지 않았는 지, 주기적으로 친구들을 보내서 점검을 하기로 했습니다. 다만, 빠른 공사 진행을 위해 점검 시간을 1시간으로 제한했습니다. 친구들이 1시간 동안 이동할 수 있는 거리는 제각각이기 때문에, 최소한의 친구들을 투입해 취약 지점을 점검하고 나머지 친구들은 내부 공사를 돕도록 하려고 합니다. 편의 상 레스토랑의 정북 방향 지점을 0으로 나타내며, 취약 지점의 위치는 정북 방향 지점으로부터 시계 방향으로 떨어진 거리로 나타냅니다. 또, 친구들은 출발 지점부터 시계, 혹은 반시계 방향으로 외벽을 따라서만 이동합니다.
외벽의 길이 n, 취약 지점의 위치가 담긴 배열 weak, 각 친구가 1시간 동안 이동할 수 있는 거리가 담긴 배열 dist가 매개변수로 주어질 때, 취약 지점을 점검하기 위해 보내야 하는 친구 수의 최소값을 return 하도록 solution 함수를 완성해주세요.

 

정답

from itertools import permutations

def solution(n, weak, dist):
    answer = 0 
    length = len(weak)
    for i in range(length):
        weak.append(weak[i]+n) # 취약지점 길이를 2배로 늘려 각 취약지점에서 한바퀴씩 돌 때 확인할 취약지점을 저장
    answer = len(dist) + 1
    
    for start in range(length):  # 0-23 을 시작지점으로 반복
        for friends in list(permutations(dist,len(dist))): # 만들 수 있는 조합에서 한 조합 꺼내기(순열) , ex) [5,3,7]
            count = 1 # 친구 수, 1명으로 시작해서 모든 취약지점을 체크하지 못하면 1명씩 추가됨
            position = weak[start] + friends[count-1] # 한 친구가 갈 수 있는 마지막 지점
            
            for index in range(start, start+length): #시작지점부터 한바퀴 돌때까지 (취약지점검사)
                if position < weak[index]:
                    count += 1
                    if count > len(dist) : # 투입된 친구 수가 존재하는 친구 수보돠 많다면 종료
                        break
                    position = weak[index] + friends[count-1] #포지션을 다시 초기화 
            answer = min(answer,count) #투입할 친구의 최소값 갱신
            
    if answer > len(dist): # 최소값이 친구 수보다 많다면 -1 출력 < 문제조건
        return -1
    return answer

 

풀이

두시간동안 풀어봤지만 역시 카카오는 어려워.. 바아로 답지 ㄱㄱㄹ..

 

일단 문제를 풀 때 어떤 식으로 취약지점을 확인하고, 친구 수를 최소로 할 지 아이디어를 몇 개 떠올려 봤는데 

모두 원이라는 제한조건 때문에 어려움이 있었다.

 

문제를 풀기 위해 필요한 핵심은 바로 취약지점의 길이를 두 배로 늘리는 것이었는데

원형을 일자 형태로 늘려 계산을 쉽게 할 수 있었다..!!!

그리고 친구의 수만큼 친구를 배치하는 모든 경우의 수를 계산하여 -> 순열(permutations 내장 라이브러리) 사용

답을 구하는 문제였음. 이렇게만 보면 나도 이해하기 어려우니까 다시 정리해보자.

 

 

풀이순서

1. 원형을 일자로 만들기 위해 취약지점의 길이를 2배로 늘린 변수를 생성

(예를 들어 n=12, 취약지점 weak = [1,3,6,9] 일 떄, 두배로 늘린 취약지점은 weak = [1,3,6,9,13,15,18,21] 이 될 것임. 그리고 각 취약 지점 1,3,6,9를 하나씩 시작점으로 정해 한바퀴 돌린다고 생각하면 1부터 13까지, 3부터 15까지, 6부터 18까지, 9부터 21까지취약지점을 체크할 수 있게 된다.)

 

2. 첫 번째 for문:

시작 지점부터 한바퀴 돌면서 취약지점을 검사할건데, 어디부터 시작할건지 시작점을 취약지점의 원래 길이까지 for문으로 돌린다. 

(각 지점에서 시작했을 떄마다 투입할 친구의 최소값이 갱신될 것임.)

 

3. 두 번째 for문 : 

만들 수 있는 친구의 투입 조합 리스트를 생성해 하나씩 꺼내면서 특정 지점에서 시작했을 떄 + 각 친구 조합마다 몇 명의 친구가 필요한지를 확인

이 떄, 첫 번째 친구가 투입되었을 때 그 친구가 도착할 지점(시작지점+이동할 수 있는 거리)을 계산해 변수에 초기화 해둠

# permutations을 사용한 순열 
from itertools import permutations

dist = [3,5,7]

data = list(permutations(dist,len(dist)) # dist에서 dist의 길이인 3개를 뽑아 순서를 고려하여 나열하는 경우의 수 집합
# data = [(3, 5, 7), (3, 7, 5), (5, 3, 7), (5, 7, 3), (7, 3, 5), (7, 5, 3)]

# for문을 돌 때마다 friends는 data의 요소들을 차례대로 가리킴

 

4. 세 번째 for문 : 

이제 시작지점부터 한바퀴를 돌면서 취약지점을 검사한다. 

- 만약 한 친구가 갈 수 있는 길이(도착지점)가 취약지점을 지나쳤다면, 다시 for문을 돌며 최대로 확인할 수 있는 취약지점을 찾는다. 

- 먄약 한 친구의 도착지점이 특정 취약지점보다 작으면 그 친구는 해당 취약지점을 검사할 수 없다는 뜻이며 다음 순서의 친구가 투입된다.

- 다음 순서의 친구가 투입된다면, 친구의 수를 +1 시키고 해당 취약지점부터 그 친구가 갈 수 있는 도착지점을 갱신한다.

- 한 바퀴를 다 돌며 취약지점을 모두 검사했다면 필요한 친구 수를 갱신한다(이전과 비교해 더 작은 값을 저장)

- 결국 특정 시작지점에서의 모든 친구 경우의수를 돌며 계산한 필요한 친구의 최소값이 도출된다.

 

참고

이것이 취업을 위한 코딩테스트다. (with.python)