외벽점검 Python 정리 및 구현 (카카오 기출)

외벽 점검

프로그래머스: https://school.programmers.co.kr/learn/courses/30/lessons/60062

Edge case

1. 문제조건

• 글을 꼼꼼히 읽고 문제를 풀자

---

Code

1. 1트

시간초과

• 인원수별로 시작 자리 weak 배열 내의 원소에서 permutation으로 지정한 뒤
• 모든 weak이 다 찼는지 확인하는 코드

# 외벽 점검
# https://school.programmers.co.kr/learn/courses/30/lessons/60062
# 1트
# 11:22 - 12:00
# 시간 초과

from itertools import permutations

def solution(n, weak, dist):

    c = [0] * n
    dist.sort(reverse=True) # 범위가 넓은애부터 소환
    wl = len(weak)
    for i in range(1, len(dist)+1):  # 일꾼의 수 만큼 반복 // i = 1, 2, 3, 4
        for j in permutations(weak, i):   # 자리 지정  // j = [[0], [1], [2], [3], [0, 1], [0, 2], [0, 3], [1, 0], [1, 2], ...] // i개 만큼 위치를 뽑아놓음
            for k in range(i):
                for m in range(j[k], j[k]+dist[k]+1):   # j[k] 위치부터 dist[k]+1개 만큼 채워넣기 (이동은 한칸씩 더 할 수 있는거야)
                    c[m % n] = 1
            # 여기서 조건 체크. weak을 다 메꿨는지. 메꿨으면 이때 사용한 인원 i를 return 해 줘야해 // 그리고 c 행렬 초기화
            cnt = 0
            for w in weak:
                if c[w] == 1:
                    cnt += 1
            if cnt == wl:
                return i
            c = [0] * n
    return -1

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

2. 2트

22번 테스트 케이스 실패

• weak 배열을 두배로하여 늘어뜨린 뒤에, 선형적으로 체크

# 외벽 점검
# https://school.programmers.co.kr/learn/courses/30/lessons/60062
# 2트 : 위치선정을 할 때, 거리차이만큼 벌려놓고 뽑기
# 12:23 -

from itertools import permutations
def check():
    pass

def solution(n, weak, dist):

    # weak의 길이를 2배로 늘리기
    length = len(weak)
    for i in range(length):
        weak.append(weak[i] + n)
    
    answer = len(dist) + 1  # 투입할 친구수의 최솟값을 찾아나갈거임

    # 0부터 length-1 까지의 위치를 각각 시작점으로 설정
    for start in range(length):
        # 일꾼을 나열하는 모든 경우의 수 각각에 대하여 확인
        for workers in list(permutations(dist, len(dist))):
            count = 1   # 투입할 일꾼의 수
            # 해당 일꾼이 점검할 수 있는 마지막 위치
            position = weak[start] + workers[count - 1] # 시작점 부터 얼만큼까지 점검 가능한지 체크
            # 시작점부터 모든 취약 지점을 확인
            for index in range(start, start+length):
                # 점검 가능한 위치를 벗어나는 경우
                if position < weak[index]:
                    count += 1  # 새로운 친구 투입
                    if count > len(dist):   # 추가 투입이 어렵다면 종료
                        break
                    position = weak[index] + workers[count - 1]
            answer = min(answer, count)
        if answer > len(dist):
            return -1
    return answer

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