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

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

프로그래머스

 

 

문제 설명

레스토랑을 운영하고 있는 "스카피"는 레스토랑 내부가 너무 낡아 친구들과 함께 직접 리모델링 하기로 했습니다. 레스토랑이 있는 곳은 스노우타운으로 매우 추운 지역이어서 내부 공사를 하는 도중에 주기적으로 외벽의 상태를 점검해야 할 필요가 있습니다.

 

레스토랑의 구조는 완전히 동그란 모양이고 외벽의 총 둘레는 n미터이며, 외벽의 몇몇 지점은 추위가 심할 경우 손상될 수도 있는 취약한 지점들이 있습니다. 따라서 내부 공사 도중에도 외벽의 취약 지점들이 손상되지 않았는 지, 주기적으로 친구들을 보내서 점검을 하기로 했습니다. 다만, 빠른 공사 진행을 위해 점검 시간을 1시간으로 제한했습니다. 친구들이 1시간 동안 이동할 수 있는 거리는 제각각이기 때문에, 최소한의 친구들을 투입해 취약 지점을 점검하고 나머지 친구들은 내부 공사를 돕도록 하려고 합니다. 편의 상 레스토랑의 정북 방향 지점을 0으로 나타내며, 취약 지점의 위치는 정북 방향 지점으로부터 시계 방향으로 떨어진 거리로 나타냅니다. 또, 친구들은 출발 지점부터 시계, 혹은 반시계 방향으로 외벽을 따라서만 이동합니다.

 

외벽의 길이 n, 취약 지점의 위치가 담긴 배열 weak, 각 친구가 1시간 동안 이동할 수 있는 거리가 담긴 배열 dist가 매개변수로 주어질 때, 취약 지점을 점검하기 위해 보내야 하는 친구 수의 최소값을 return 하도록 solution 함수를 완성해주세요

 

제한 사항

• n은 1 이상 200 이하인 자연수입니다.
• weak의 길이는 1 이상 15 이하입니다.
  • 서로 다른 두 취약점의 위치가 같은 경우는 주어지지 않습니다.
  • 취약 지점의 위치는 오름차순으로 정렬되어 주어집니다.
  • weak의 원소는 0 이상 n - 1 이하인 정수입니다.
• dist의 길이는 1 이상 8 이하입니다.
  • dist의 원소는 1 이상 100 이하인 자연수입니다.
• 친구들을 모두 투입해도 취약 지점을 전부 점검할 수 없는 경우에는 -1을 return

 

 

처음 접근 및 코드

1. 배열 dist 중 가장 큰 원소부터 순서대로 외벽 수리를 맡긴다.
2. weak를 순회하면서 맡을 수 있는 번호를 check 안에 넣는다.
   1. 만약에, weak에서 popleft한 값이 check의 첫번째 항과 거리 차이가 d 보다 큰 경우, 거리차이가 d보다 작거나 같을 때까지 check를 popleft하여 다시 weak에 append한다. 
3. 이 동작을 수행할 때마다 남은 weak 원소의 거리 차이를 구하여 합이 가장 낮은 경우를 채택하여 적용한다.

from collections import deque

def solution(n, weak, dist):
    answer = 0
    walls = deque(weak)
    dist.sort(reverse=True)
    member = 0
    
    for d in dist:
        check = deque([])
        maximum = max(walls)
        best = 1e9
        left = []
        while walls:
            m = walls.popleft()
            
            if len(check):
                k = check[0]
                distance = m-k if m > k else m-k+n
                
                if distance > d:
                    while check:
                        out = check.popleft()
                        walls.append(out)
                        
                        if check:
                            k = check[0]
                            distance = m-k if m > k else m-k+n
        
                        if distance <= d:
                            break
                    
                    if out == maximum:
                        break
                        
            check.append(m)
            if len(walls) == 0:
                member += 1
                return member
            
            next = []
            for i in range(len(walls)):
                diff = walls[i] - walls[i-1] if walls[i] > walls[i-1] else n + walls[i] - walls[i-1]
                next.append(diff)
            
            efficient = min(sum(next[1:]), sum(next[:len(next)-1]))
            if efficient < best:
                best = efficient
                left = deque(walls)
                
        member += 1
        walls = deque(left)

        if len(walls) == 0:
            return member
    
    if len(walls):
        return -1
    return answer

 

 

처음 접근의 문제

1. check에 넣을 때마다 확인하는 로직이 너무 복잡함.
2. 그리고 확인할 때의 나머지 weak의 거리 차 합을 구하는 방식은 100% 보장된 로직이 아님

결론은 100% 보장된 로직이 있어야 한다는 것이고 백트래킹으로 풀 수 없다.

그렇기 때문에 모든 경우를 고려하면서 시간을 초과하지 않는 로직이 필요

 

 

정답 코드 및 풀이방식

1. 원형의 weak 배열을 선형으로 풀어내기 위해서 같은 배열 1개 더 붙인다.
2. 그리고, dist 배열의 모든 경우의 수를 permutations로 구한다.
   
   1. 처음 weak의 어떤 index에서 시작할 지에 대한 weak[start]를 정한다.
   2. 그다음, 그 친구가 어디까지 처리할 수 있을지를 position = weak[start] + 친구가 이동할 수 있는 거리
   3. weak의 원소를 순회하면서 position과 값을 비교한다.
      1. 이 때, weak의 원소가 더 큰 경우, 필요한 친구 수를 +1 한다.
      2. 그리고 position을 해당 weak 원소 + 그 다음 친구가 이동할 수 있는 거리로 다시 재정의 한다.
   4. weak를 모두 순회한 후, count 값이 가장 낮은 경우를 최소값으로 정의하여 return
   5. count가 dist의 원소개수보다 많은 경우, -1을 return

from itertools import permutations

def solution(n, weak, dist):
    length = len(weak)
    weak = weak + [w + n for w in weak]
    answer = len(dist) + 1
    
    # dist의 모든 경우의 수
    for friends in permutations(dist):
    	# weak의 어떤 index에서 시작할지
        for start in range(length):
            count = 1
            position = weak[start] + friends[count - 1]
            
            # weak 전체 원소를 순회
            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

 

 

느낀 점

• 백트래킹을 시도할 때, 로직이 너무 복잡해지고 불확실해지는 경우 과감히 포기하고 모든 경우의수를 고려할 수 있는 방법을 찾아야한다.
• 그래서 제약조건을 잘 생각해서 다양한 라이브러리를 활용할 줄 알아야 함.
• 알고리즘에 유용한 라이브러리들을 알아보고 적용해야겠다.