[이분 검색] 외벽 점검 (파이썬, 카카오)

문제 설명

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

프로그래머스

문제 풀이

• 원형 레스토랑을 일직선으로 생각해서 기존 weak을 두배로 늘려줌
  • eg) weak = (1,3,5,7) 이라면 각 원소에 n(12이라고 가정)을 더해줌
  • weak = [1,3,5,7,13,15,17,19]
• 처음에는 가장 긴 dist 원소부터 출발 지점에만 넣고 이후 짧은 dist들을 차례로 넣으면 되는 줄 알았는데 그럴 경우 예외가 생김 ( eg. 짧은 간격에 있는 weak을 짧은 dist로만 처리하면 되는데 굳이 긴 dist를 넣어서 처리하면 이후 긴 weak 간격을 처리하지 못하는 경우 ) 
• 따라서 dist를 순서가 필요한 조합인 순열로 처리해서 모든 경우를 탐색해봐야함
• 이때, 현재 잡고 있는 dist가 몇 개의 weak을 처리 할 수 있는지 빠른 시간으로 처리하기 위해 이분 검색인 bisect을 활용
• weak 인덱스인 cur_idx, dist의 인덱스인 d_idx를 두면 현재 dist로 어느 지점까지 탐색 가능한지 알 수 있음
  • end = weak[cur_idx] + dist[d_idx] 
• e_ idx = bisect_left( weak, end ) 를 구하면 이 dist 가 어느 인덱스까지 처리 가능한 지 계산
  • 위에서 구한 end 값이 5이고 weak이 [1,3,5,7] 이라면 e_idx 는 2 가 나옴. 
  • 만약 cur_idx 가 0 이라면 탐색 가능한 갯수는 1,3,5이므로 3개가 나와야함. 따라서 end가 weak에 있는 요소일 경우 탐색 가능한 갯수는 e_idx - cur_idx + 1 을 해줌
  • end값이 6이라면 e_idx는 3이 나와서 탐색 가능한 갯수는 e_idx-cur_idx 인 3 임
• 한번의 dist를 처리 했으므로 다음 dist 요소를 큐에 담아줘서 계산 해줌
• 지금까지 처리한 weak 갯수인 cnt가 처음에 받은 weak 갯수와 같다면 계산은 끝

소스 코드

from bisect import bisect_left
from collections import deque
from itertools import permutations

# arr = [1,3,4,9,10,13,15,16,21,22]
# print(bisect_left(arr,4))


def solution(n, weak, dist):
    answer = 9 	#dist의 최대 길이는 8이므로 answer는 9라고 처음에 넣어 줬음
    w = len(weak)
    q = deque()
    dist.sort(reverse=True)
    dists = list(permutations(dist,len(dist)))
    for i in range(w):
        weak.append(weak[i]+n)
        

    for dis in dists:
        for i in range(w):
            q.append((0,i,0))
        while(q):
            cnt, cur_idx, d_idx = q.popleft()

            if cnt==w:
                answer=min(answer,d_idx)
                continue
            if cur_idx>=w or d_idx>=len(dist):
                continue
            
            cur,d = weak[cur_idx], dis[d_idx]
            end= cur+d
            e_idx = bisect_left(weak,end)
            temp = e_idx-cur_idx
            if weak[e_idx]==end:
                q.append((cnt+temp+1,e_idx+1,d_idx+1))
            else:
                q.append((cnt+temp,e_idx,d_idx+1))
        
    return answer if answer!=9 else -1

    
print(solution(	12, [1, 3, 4, 9, 10], [3, 5, 7]))