기둥과 보 설치[2020 KAKAO BlIND RECRUITMENT]

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

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

 

접근 방법 :

* 나머지 연산을 생각했었다. 원형의 특성상 나머지 연산을 통해 방향에 상관없이 인덱스에 접근할 수 있을것 같았다. 

* 배열을 두개를 붙여야 겠다고 생각했다. 나머지 연산은 계산이 너무 복잡해 질것 같았다. 전체 크기만큼 붙인 인덱스를 뒤에 연이어 붙여주기만 하면 될것 같았다.

 

두번째 방법으로 코드를 짜보았다. 살펴보도록 하자!

from itertools import permutations

def solution(n, weak, dist):
  answer = len(dist) + 1
  weak_length = len(weak)
  for i in range(weak_length) :
    weak.append(weak[i] + n)
  
  dist_permutations = list(map(list,permutations(dist, len(dist))))

  for i in range(weak_length) :
    # 시작점을 달리해주어서 구간을 만들어 버린다
    temporary_range = [weak[j] for j in range(i, i + weak_length)]

    for dist_permutes in dist_permutations :
      result = 1
      friend_index = 0
      checked_length = temporary_range[0] + dist_permutes[friend_index]
      for k in range(weak_length) :
        if temporary_range[k] > checked_length :
          result += 1
          
          # 친구들 수 보다 커지면 종료 해야지
          if result > len(dist_permutes) :
            break
          
          friend_index += 1
          # 이 부분이 어려웠다.
          checked_length = temporary_range[k] + dist_permutes[friend_index]
      
      answer = min(answer, result)
  return answer


n = 12
weak = [1, 5, 6, 10]
dist = [1, 2, 3, 4]
print(solution(n, weak, dist))

n = 12
weak = [1, 3, 4, 9, 10]
dist = [3, 5, 7]
print(solution(n, weak, dist))

 

알게된 점 

* permutaions 라이브러리는 굉장히 쓸모가 많다 (permutations(배열, 숫자)) => 숫자의 크기만큼 순열 다 뽑아내 준다.

* 검사한 구간의 크기를 기존의 값이 아닌 새로 검사할 구간으로 해야한다.(이미 기존의 구간은 검사한것이기 때문에 새로운 구간을 기준으로 설정하는 것이 맞다)