Q14. 외벽 점검 (2020 카카오 기출)

코딩테스트 연습 - 외벽 점검 | 프로그래머스 (programmers.co.kr)

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

 

문제 읽어보니까 좀 빡세네? 20분만 고민해보도록 하자. 

 

내가 고민한 결과

일단 n은 최대 200, weak는 최대 15, dist는 최대 8

뭔가 숫자들이 좀 작다? ㅎㅎ

바로 전체탐색 방법부터 해본다.

k를 1부터 늘려가면서

k명을 선택하는 경우의 수를 다 계산해보고

weakness가 다 커버되면 k를 리턴하는 것이다.

dist는 클수록 좋으니까 내림차순으로 정렬해놓고 큰 순서대로 뽑으면 될듯?

 

def selectk(weaknum,people):
    #return k length list of weakpoint i
    
    def perm(n,k,tmp,permlist):
        if k == 0:
            permlist.append(tmp[:])
            return
        
        for i in range(n):
            if i not in tmp:
                tmp.append(i)
                perm(n,k-1,tmp,permlist)
                tmp.pop()
                
    permlist = []
    perm(weaknum,people,[],permlist)
    
    return permlist

def is_valid(n, weak, dist, candidates):
    print(len(candidates[0]),"명일 때")
    for i in range(len(candidates)):  
        weakcheck = [False] * len(weak)
        c = candidates[i]
        #print("weakness 후보",c)
        
        for j in range(len(c)):
            #print(j,"번째 사람",weak[c[j]],"에서",dist[j],"만큼 갈 수 있음")
            for k in range(dist[j]+1):
                curpos = (weak[c[j]] + k) % n
                if curpos in weak:
                    #print(curpos,"인덱스 weakness 비활성화")
                    weakcheck[weak.index(curpos)] = True
        
        if all(weakcheck):
            return True
                
                
    return False
    
def solution(n, weak, dist):
    dist.sort(reverse=True)
    
    for people in range(len(dist)):
        candidates = selectk(len(weak), people+1)
        if is_valid(n, weak, dist, candidates):
            return people+1
    
    return -1

 

 

코드도 개복잡하고 결과는 TLE 폭탄

 

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

정답을 읽어보자~

 

1. 원형을 늘려서 일자 형태로 만든다. (취약한 지점을 2번 나열)

2. 각 친구를 나열하는 모든 경우의 수를 계산한다.]

 

원형을 늘린다는거 빼고 아이디어는 비슷한데 나는 왜 tle가 뜨지!?

is_valid가 너무 비효율적이어서 그런가 ㅋㅋㅋ

하긴 고차원의 리스트 연산을 너무 많이 써먹긴했다.

 

일단 문제풀 때 시간을 줄여줄 itertools의 permutations를 알아보자

 

굉장히 사용하기 쉽고 좋은 라이브러리!

 

저자분의 코드

from itertools import permutations
    
def solution(n, weak, dist):
    length = len(weak)
    for i in range(length):
        weak.append(weak[i] + n)
        
    answer = len(dist) + 1
    
    for start in range(length):
        for friends in list(permutations(dist, len(dist))):
            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]
            answer = min(answer,count)
    
    if answer > len(dist):
        return -1
    
    return answer
    
    return -1

 

이해가 쉽지가 않네..

일단 가장 바깥쪽 반복문은 모든 취약점을 시작 지점으로 해보기 위한 반복문 같다.

그 다음 반복문은 친구들이 배치되는 모든 경우의 수를 고려하기 위함이고

count는 몇 명의 친구가 들어가야되는지 세기 위함

position은 현재 친구가 점검할 수 있는 마지막 지점

그 다음 반복문은 한 바퀴를 돌면서 현 친구가 점검할 수 있는 마지막 지점을 넘어가는 취약점이 있나 보는것이다. 있으면 새 친구를 투입해야 되니까 count를 ++하고 count가 친구 수보다 많아지면 못한다는거니까 break. position은 다음 취약점 구간으로부터 그 친구가 갈수있는 곳까지로 업데이트 한다.

 

이것도 나중에 다시 풀어봐야겠다. 답지의 도움을 받았으니..

그래도 나도 정확성 면에서는 틀리지 않았다?ㅠㅠ