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

1. 문제

• 프로그래머스 문제와 동일

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

• 외벽

  • 동그란 모양, 둘레는 n, 취약지점이 있다.

• 점검시간은 1시간

  • 친구들 1시간 이동거리는 제각각

• 최소한 친구들 투입하여 취약지점 점검, 나머지 친구들 내부 공사

• 레스토랑 정북 방향 지점을 0

• 취약 지점의 위치는 정북 방향 지점으로부터 시계 방향으로 떨어진 거리로 나타낸다.

• 친구들은 시계 혹은 반시계 방향으로 외벽을 따라서만 이동

• 입력

  • 외벽의 길이 n, 취약 지점의 위치가 담긴 배열 weak, 친구가 1시간 동안 이동할 수 있는 거리 dist

• 출력

  • 취약 지점을 점검하기 위해 보내야 하는 친구 수의 최소값

• 제한

  • n 은 1 <= n <= 200
  • weak 는 1<= weak <=15
    • 취약점이 위치가 같은 경우는 없다.
    • 취약 지점의 위치는 오름차순 정렬
    • weak는 0 이상 n-1이하인 정수
  • dist 는 1<= dist <=8
    • 원소는 1 <= dist <=100
  • 친구들을 모두 투입해도 전부 점검할 수 없는 경우 -1

입출력 예

2. 아이디어

• 문제에서 주어지는 원소의 숫자가 작아서 완전탐색 문제인듯 하다.
• 원형을 선형으로 바꾸어준다. 두배로 늘리면, 원래 순서의 맨 마지막부터 탐색해도 두배로 늘린 리스트의 끝까지는 갈 수 없으니 탐색이 가능하다. (대체 이런건 어떻게 생각할까?)
• weak를 순서와 거리 개념으로 동시에 생각.
• 친구들을 순열로 줄을 세운 경우를 탐색하는데, 친구가 모든 점검부위를 못 커버하면 더 투입한다. (말은 참 쉽다.)
  • 모든 지점에서 출발을 하게 해보면서
    • 친구의 순서 경우 마다 (순열, permutations)
      • 한 친구가 커버 못하면, 더 넣어보고, 주어진 친구수를 넘으면 탐색을 그만한다.(못한다.)
      • 친구 더 넣어서 커버가능하면 친구수를 구한다. (반복하면서, 최소의 친구수를 갱신한다.)

3. 예제코드

from itertools import permutations
def solution(n, weak, dist):
    # 취약점의 길이를 2배로 늘려서 원형을 일자 형태로 변경한다.
    length = len(weak)  # 취약점의 길이
    # 취약점 길이 연장, 직선의 좌표처럼 활용
    weak = weak + [w + n for w in weak]  # 리스트 컴프리헨션 연습
    # 정답 초기화 : 최소값 구하는 중이니까, 가장큰수보다 더 크게 세팅
    answer = len(dist) + 1
    # 완전탐색
    for start in range(length): # 모든 시작지점에서 출발시키는 경우 고려
        # 모든 친구들의 순열의 경우 탐색, 친구들이 어떤 순서로 나가는가 
        for friends in list(permutations(dist, len(dist))):  
            # 친구투입수 초기화 1명 먼저 투입
            count = 1  # 친구투입수이면서, 친구리스트에서 친구 뽑아낼 인덱스로도 사용 (이런게 생각해내기 어려움)
            # 친구 투입 판단 기준 생성 : 한 친구가 커버 가능한 위치 (결점 한 곳에서 출발해서 이동한 위치)
            position = weak[start] + friends[count-1]   
            
            # 친구 몇 명 넣을지 보는 판단 
            # 취약지점 확인 : 친구가 투입되는 위치(start)부터 전체 취약지점(start + length) 을 본다. 
            # 그리고 인덱스로 위치를 확인(weak리스트에서)하고, 판단기준(position)보다 큰지 확인.
            for index in range(start, start + length):  
            # 이중 for문 바깥의 돌리는 숫자 가져와서 또 사용하는 것, 이것도 생각하기 어려움.
                if position < weak[index] : # 모든 취약지점 중 하나라도 한 친구가 커버가능한 범위를 벗어나면
                    count += 1   # 새로운 친구를 투입한다. (친구수 기능 + 친구 뽑아 내는 인덱스 기능 동시)
                    if count > len(dist): 
                    # 새로운 친구 투입수가 원래 친구수보다 많으면, 취약지점 확인이 안되는 거니까, 
                    # 취약지점 확인 for문을 나간다. (어디를 나가는지 봐야지)
                        break
                    # 친구 투입에 문제가 없다면 (원래 친구수 안에서 투입가능하면)
                    # 한 친구로 커버 안되는 취약지점의 위치에서 (weak[index]의 의미) 
                    # 추가로 투입한 친구의 커버 가능범위를 더해서 커버가능한 범위를 갱신
                    position = weak[index] + friends[count-1]
            # 정답 갱신 : 모든 친구의 순열 경우 마다 최소값 갱신 
            answer = min(answer, count) 
            
    if answer > len(dist):  # 정답이 친구수를 넘어갔으면 , -1 내보낸다.
        return -1 
    return answer # 그렇지 않으면, 정답을 내보낸다.

4. 느낀점

• 왜 이렇게 어렵지? 싶어서 카카오 테크블로그에 들어가보니, 정답율 0.6%, 100명 풀어도 1명도 제대로 못푼다. 너무 낙심말자.
  • 카카오 테크블로그 코딩테스트 해설집 링크에 정답율 나옴.
    링크 : https://tech.kakao.com/2019/10/02/kakao-blind-recruitment-2020-round1/
• 다시 문제풀이를 순서대로 떠올리기조차 어렵다.
• 읽고, 쓰고 하다보면 언젠가 생각해낼 수 있으려나. 근데 변형된 문제는 풀겠나?...

참고

• 이것이 취업을 위한 코딩테스트다. with 파이썬