[이코테] 구현 - 외벽 점검

해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 

 

---

문제설명

하단의 링크를 참조하자.

https://programmers.co.kr/learn/courses/30/lessons/60062

코딩테스트 연습 - 외벽 점검

사고과정

• 완전탐색이라는 것을 눈치를 채긴했다.. 주어진 데이터 범위가 워낙 작아서 말이다.. 그런데 문제는 원형으로 된 정보를 어떻게 하느냐에서 감이 오지 않아 포기했다.. 결국 풀이를 염탐했음!
• 우선 문제에서 배우는 팁을 잠깐 정리해보자.
  • 주어진 데이터 범위가 작게 주어지면 완전 탐색을 생각할 것!
  • 원형으로 나열된 데이터를 처리하는 경우, 그 데이터의 길이를 2배로 늘려서 원형을 일자 형태로 만드는 작업을 하자!
• 위에서 두번째가 풀이에 핵심이었다. 그래서 풀이과정을 단계별로 도식화하면 다음과 같다.
• 1. 원형 -> 일직선으로 나타내기 위해 2배로 늘리기
• 2. 주어진 친구들 경우의 수를 완전탐색하기 위해 순열 활용(조합으로 착각하면 안됨. 순서 고려해야 함!)
• 3. 외벽 점검 시작하는 최초 시작점 탐색 -> 시작점 1개당 친구들 경우의 수 탐색 -> 시작점 1개당 친구들 경우의 수 1개당 필요인원 탐색. 결국, 총 3중 반복문 수행
• 소스코드만 봐서 이해가 안되서 아래처럼 일일이 코드를 연습장에 써보았다. 힘은 들었는데 1번 작성해보니까 이해가 퐉! 되었다..! 이것도 한 10번 이상은 풀어봐야겠다.. 너무 어렵..

풀이(스스로 못 푼 풀이)

from itertools import permutations

def solution(n, weak, dist):
    length = len(weak)
    # 원형 맵 일직선 상에 구현하기 위해서 길이 2배로 늘리기
    for i in range(len(weak)):
        weak.append(weak[i] + n)
    # 최소 인원 계산할 최댓값 정의 for 그리디
    answer = len(dist) + 1
    # 2배 늘린 일직선 상 맵에서 시작점 하나씩 탐색(단, 원래 취약지점 길이까지만 탐색)
    for start in range(length):
        # 한 시작점에서 투입할 수 있는 친구 경우의 수 하나씩 탐색(순열)
        for friends in list(permutations(dist, len(dist))):
            # 최초의 친구 1명 투입!
            count = 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]
            # 다 탐색했을 때의 count(인원 수)를 최솟값으로 업데이트
            answer = min(answer, count)
    # 다 처리하기 전 친구를 다 썼으면 -1
    if count > len(dist):
        return -1
    return answer