[programmers] 구현 - 외벽점검

문제링크

---

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

문제 설명

---

둘레가 n인 레스토랑의 외벽을 점검하는데, 외벽의 몇군데에 취약 지점이 있음. 친구들을 보내 점검을 하는데 각 친구마다 이동할 수 있는 거리가 다르고, 시계 혹은 반시계방향으로 이동 가능

IN

• n : 외벽의 길이
• weak : 취약지점의 위치 (레스토랑의 위치 0에서부터 시계방향으로 얼마나 떨어졌는지)
• dist : 각 친구들의 1시간동안 이동할 수 있는 거리

OUT
취약지점을 점검할 수 있는 최소 친구 수

제약사항

• 1≤ n ≤ 200
• 1≤ len(weak) ≤ 15 (오름차순 정렬)
• 1≤ len(dist) ≤ 8
  
  

문제 풀이

---

시도 1

최소 친구수를 구하는거니까 greedy를 이용해서 가장 이동가능한 거리가 긴 친구부터 계산을 하려고 했다. 1명의 친구가 점검하는 경우부터 포문을 돌렸고, k번째 취약점부터 이동거리가 제일 긴 친구가 시계방향으로 체크하는 경우를 계산했다.

def solution(n, weak, dist):
    answer = n+1
    dist.sort(reverse=True)
    print(dist)

    for i in range(1, len(dist)+1):
        #i명의 친구가 점검하는 경우
        print(i, "명의 친구")
        
        #k번째 취약점부터 체크하기
        for k in weak:
            fixed = {}
            cur = k
            for w in weak:
                fixed[w] = 0
            #이동거리 제일 많은 친구가 k번째부터 시계방향으로 체크 
            for j in range(i):
                idx = cur + dist[j]
                print(j, cur, idx)

                #w부터 idx까지 전부 수리 완료 
                if idx > n:
                    for l in weak: 
                        if l in range(0, idx%n+1):
                            fixed[l] = 1
                        elif l in range(k,n-1):
                            fixed[l] = 1
                else:
                    for l in weak:
                        if l in range(k,idx+1):
                            fixed[l] = 1
                print(fixed)
                #다음으로 고칠 취약지점
                tmp = [k for k in weak if k > idx%n] 
                if len(tmp) == 0:
                    cur = weak[0]
                else:
                    cur = min(tmp)

            if 0 not in fixed.values():
                if i < answer:
                    answer = i

    return answer if answer != n+1 else -1

→ 문제점 : 이 방법으로 계산하면 친구가 무조건 외벽을 순서대로 점검해야함 → 그리디로 풀 수 없음

시도 2

dfs를 응용해서 풀어보았다.

def fixing(N, weak, dist, fixed, count, num):
    #i번째 친구부터 체크하기
    if 0 not in fixed.values():
        return True
    if num >= count:
        return False
    for w in weak:
        if fixed[w] != 1:
            #k부터 idx까지 전부 수리 완료 
            idx = w + dist[num]
            if idx > N:
                for l in weak: 
                    if l in range(0, idx%N+1):
                        fixed[l] = 1
                    elif l in range(w,N-1):
                        fixed[l] = 1
            else:
                for l in weak:
                    if l in range(w,idx+1):
                        fixed[l] = 1
            #print(num, ": ", w, "- ", fixed)
            if fixing(N, weak, dist, fixed, count, num+1):
                return True
            if idx > N:
                for l in weak: 
                    if l in range(0, idx%N+1):
                        fixed[l] = 0
                    elif l in range(w,N-1):
                        fixed[l] = 0
            else:
                for l in weak:
                    if l in range(w,idx+1):
                        fixed[l] = 0
            

def solution(n, weak, dist):
    dist.sort(reverse=True)
    fixed = {}
    for w in weak:
        fixed[w] = 0

    for i in range(1, len(dist)+1):
        #i명의 친구가 점검하는 경우
        if fixing(n, weak, dist, fixed, i, 0):
            return i

    return -1

print(solution(12,	[1, 5, 6, 10],	[1, 2, 3, 4]))

시간초과가 난다 ㅜ ㅜ

정답코드

문제 해결 포인트

1. 원형으로 구성된 취약점들을 길이 2배로 늘려 원형→일자
2. 친구를 무작위로 나열하는 경우의 수를 각각 확인

import itertools 

def solution(n, weak, dist):
    dist.sort(reverse=True)
    length = len(weak)

    #길이 2배인 일자 리스트로 바꾸기
    for i in range(length):
        weak.append(weak[i]+n)
    print(weak)
    answer = len(dist)+1

    #0부터 length-1까지 시작점
    for start in range(length):
        for friends in list(itertools.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

어렵다,, 다시풀어봐야지

원형은 길이 두배인 일자리스트로 풀 수 있다