[프로그래머스] 외벽 점검

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

문제 분석

• 취약 지점이 존재하는 범위 n이 주어진다
• 취약 지점 배열 weak이 주어진다
• 취약 지점을 점검할 친구들이 움직일 수 있는 거리 배열 dist가 주어진다
• 최소한의 친구들을 보내 점검할 수 있는 것이 목표이다
• 친구가 최소 몇 명 필요한지, 혹은 모든 친구를 동원해도 점검이 불가하다면 -1을 반환한다.

---

알고리즘 설계

• 이 문제의 경우 combinations 함수로 해결할 수 있겠다는 생각이 들었다
• 주어진 친구들의 조합을 모두 생성해, 이를 검사하는 함수로 보낸다
• 검사하는 함수의 경우 취약 지점의 첫 번째 항목의 값에 dist의 값을 더한 값만큼 배열에 추가한다
  • 만약 첫 번째 취약 지점의 값이 2이고, 첫 번째 친구의 점검 가능 거리가 3이라면 2부터 5까지의 값을 sol 배열에 추가한다
• 만약 두 번째 항목의 값이 sol 배열에 존재하는 값이라면, 다음 항목의 값으로 넘어간다
• sol 배열에 모든 취약 지점에 해당하는 값이 존재하는지 검사하고, 존재하면 ans에 해당 dist 배열을 추가한 뒤 함수를 탈출한다
• ans 배열에 비어 있다면 -1을, 그렇지 않다면 첫 번째 항목의 길이를 반환한다

---

오답 코드

왜요?

from itertools import combinations

def find_solution(n, weak, dist, ans):
    for i in range(len(weak)):
        check = False
        sol = []
        index = i
        for j in dist:
            while weak[index] in sol:
                index = (index + 1) % len(weak)
            for k in range(weak[index], weak[index] + j + 1):
                if (k % n not in sol):
                    sol.append(k % n)
            if all(w in sol for w in weak):
                check = True
                break
        if check == True:
            ans.append(dist)
            break
            
def solution(n, weak, dist):
    dist_comb = []
    ans = []

    for i in range(1, len(dist) + 1):
        comb = combinations(dist, i)
        dist_comb.extend(comb)

    for dist in dist_comb:
        find_solution(n, weak, dist, ans)

    if not ans:
        return -1
    else:
        return len(ans[0])

뭐가 문제였을까?

순열을 계산하지 않음

n = 16
weak = [1,2,3,4,5,7,8,10,11,12,14,15]
dist = [4,2,1,1]

• 위 테스트 케이스에서 [4, 1, 2, 1] 순서를 통해서 가능하므로 결과는 4가 출력되어야 한다
• 하지만 실행해보면 -1이 출력되는 것을 확인할 수 있다
• 이는 [4, 2, 1, 1]에 대해서만 검사를 수행하고 있기 때문이다
• 따라서 combination으로 조합한 뒤, permutation으로 순열까지 생성해서 모두 검사해야 한다
• 이 경우 얼마나 중복을 줄이고, 불필요한 계산을 줄이느냐가 관건이 되겠다

누가 이기나 해보자

정답 코드

from itertools import combinations, permutations

def find_solution(n, weak, dist, ans):
    for i in range(len(weak)):
        sol = set()
        index = i
        for j in dist:
            while weak[index] in sol:
                index = (index + 1) % len(weak)
            for k in range(weak[index], weak[index] + j + 1):
                sol.add(k % n)
        if all(x in sol for x in weak):
            ans.append(dist)
            return True
    return False


def solution(n, weak, dist):
    ans = []
    for i in range(1, len(dist) + 1):
        comb = list(combinations(dist, i))
        perm = set()
        for j in comb:
            if i == 1:
                perm.add(j)
            else:
                perm.update(list(permutations(j, i)))

        for j in perm:
            if (find_solution(n, weak, j, ans)):
                return i
    return -1

• 여기서 핵심은 가장 최소한의 친구를 보내는 것이다
• 따라서 인원 단위로 끊어서 조합과 순열을 생성한 뒤, 검사를 수행한다
• 이 과정에서 중복을 최소화하기 위해 set을 사용한다
• 검사를 수행하는 중에도, 가능하다고 판단되면 곧바로 결과를 반환하고 종료한다

결과

효율성도 엄청 좋아졌다

• all 함수 및 permutation 함수에 대해서 알게 되었음
• 첫 제출에서 테스트 코드 하나를 실패했는데, 이거 해결하는데 3시간이 걸렸음
• 그 과정에서 파이썬 문법 및 최적화 방법에 대해서 많이 생각하고 공부함