2020 카카오 기출 - 외벽점검

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

접근

각각의 데이터의 크기가 크지 않아 완전탐색 알고리즘으로 접근하였다. n짜리의 원형의 외벽을 크기 2n짜리 배열을 생성하고, range(0,n)까의 반복문을 돌면서 i~i+n부분을 파싱하고 dist배열을 permutaations 한 값을 하나씩 순회하면서 최소갯수를 갱신해주었으나 몇몇 테스트 케이스에서 시간초과가 발생하였다.

수정

외벽이 원형의 형태로 주어졌기 때문에 이를 두배로 늘려 배열 형태로 변환하는 것은 맞다. 그러나 기준이 잘못되었음.

굳이 크기가 2n짜리인 배열을 선언하는 것이 아니라, weak의 크기 *2 만큼만 선언하여도 충분하다. 어차피 중요한것은 weak의 위치 보다는, 각 weak사이의 거리가 더 중요하기 때문에,

    for we in weak:
        newweak.append(we)
        newweak.append(we+n)
    newweak.sort()

전체 코드

from itertools import permutations
from collections import deque
def solution(n, weak, dist):
    minlength=100000
    newweak=[]
    check=len(weak)
    for we in weak:
        newweak.append(we)
        newweak.append(we+n)
    newweak.sort()
    dist_permu=list(permutations(dist,len(dist)))

    for i in range(check):
        for dist in dist_permu:
            cur_newweak=deque(newweak[i:i+check])
            dist=deque(dist)
            count=1
            curweak=cur_newweak.popleft()
            curdist=dist.popleft()
            flag=False
            while len(cur_newweak)>0:
                if cur_newweak[0]-curweak<=curdist:
                    cur_newweak.popleft()
                else:
                    curweak=cur_newweak.popleft()
                    if dist:
                        curdist=dist.popleft()
                        count+=1
                    else:
                        flag=True
                        break
            if flag:
                continue
            else:
                minlength=min(minlength,count)
    if minlength==100000:
        return -1
    return minlength
    

참고

원형은 배열로 변환, 데이터 적으면 완탐 먼저 생각