프로그래머스 외벽점검

🙂 문제 - 광고삽입

url : https://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 해주세요.

🖐풀이 방법

• 프로그래머스에서 LEVEL 3으로 나와있다.
• 각 weak 외벽들은 모두 순환 구조이다.
• n과 같은 weak 지점은 0이다.
• weak 지점을 node라고 생각한 뒤 class를 만들어 처리해 주면 될 것 같다.

Node에 들어갈 정보들
1) 자신의 weak point 지점
2) 가장 가까운 오른쪽 node지점과 거리
3) 가장 가까운 왼쪽 지점과 node의 거리
4) 완전탐색으로 순회할 것이기 때문에 방문 체크하는 flag

• 모든 weak지점에서 시작을 가정으로 완전 탐색을 이용한다.

완전 탐색
1) 지정된 노드 부터 시작하며, 왼쪽 오른쪽 순회를 각각 실행한다.
2) 주어진 방향으로 하여 누적된 거리가 주어진 거리 중 최댓값과 =,>,< 일때를 각각 체크해준다.

    - 주어진 거리 중 최댓값과 누적 거리가 같을 때 (=)
      -> 최댓값을 삭제하고 해당 노드와 옆에 있는 노드를 방문 체크 해준다.
      -> 다음 체크 대상을 옆의 노드의 옆 노드로 정의한다.
      -> 누적 거리를 초기화 시킨다
      -> 필요한 친구를 +1 한다.

    - 주어진 거리 중 최댓값이 누적 거리보다 클때 (>)
      -> 다음 체크 대상을 옆의 노드로 정의한다.
      -> 누적 거리를 더해준다.
      -> 현재 노드를 방문 체크 해준다.

    - 주어진 거리 중 최댓값이 누적 거리보다 작을 때(<)
      -> 현재까지의 누적 거리 중 주어진 거리와 가장 값의 차이가 없는 값을 삭제한다.
      -> 다음 체크 대상을 옆의 노드로 정의한다.
      -> 누적 거리를 초기화 시킨다
      -> 필요한 친구를 +1 한다.

   이렇게 모든 정보를 최신화 했을 때 만일 모든 노드를 방문하지 않았다면 dist의 길이 +1을 리턴해준다
   이는 모두 외벽 청소를 할 수 없는 경우이며 dist의 길이 +1을 한 이유는 친구가 최대로 많을 때보다 크다면 모든 경우에서 외벽청소를 할 수 없으므로 -1을 리턴하기 위함이다.

• 이렇게 정의해 놓고 오른쪽과 왼쪽으로 갔을 때 결과 값을 모두 최소값으로 초기 화 함으로써 해당 문제를 풀 수 있다.
• 물론 answer값의 초기값은 101 = (dist의 최대 길이 +1)로 설정해 두어 마땅한 값이 나오지 않으면 -1을 리턴한다.
• 해당 문제는 원형 연결 리스트를 생각하며 풀었다.
• 조건을 복잡하게 풀었지만.. 많이 어려운 문제는 아니였다...

📃 CODE

from copy import deepcopy
class Node:
    def __init__(self,me,right,left,n):
        self.me = me # 자기 자신 노드
        # 자신의 오른쪽 왼쪽 노드의 정보를 담을 공간 idx ->0 오른쪽 / 1 ->왼쪽
        # next 정보에는 오른쪽과 왼쪽 노드의 주소 정보와 거리 차이가 들어간다
        self.info = [[right],[left]]
        self.flag = False # 방문 확인을 위한 코드
        if self.me == 0: #제일 정가운데라면
            self.info[0].append(right)
            self.info[1].append(n-left)
        
        else:
            self.info[0].append(
                min(
                    abs(right-me),abs(right + (n-me))
                )
            )
            self.info[1].append(
                min(
                    abs(me-left),abs(me+(n-left))
                )
            )

#최소 근접한 거리 구하는 함수
def f_del_idx(f_dist,check_dis):
    value = 300
    idx =-1
    for i in range(len(f_dist)):
        if f_dist[i]>check_dis and f_dist[i]-check_dis<value:
            idx = i
            value = f_dist[i]-check_dis
    return idx

def find_(idx,f_nodes,distances,direct):
    need_friend = 0
    check_dis = 0

    while 1:
        root = f_nodes[idx]
        
        if root.flag == True:
            if check_dis>0:
                need_friend+=1
            break
            
        if len(distances)==0:
            break

        if check_dis+root.info[direct][1] == max(distances):
            need_friend +=1
            distances.remove(check_dis + root.info[direct][1])
            check_dis =0 
            f_nodes[root.info[direct][0]].flag = True
            f_nodes[root.me].flag = True
            idx = f_nodes[root.info[direct][0]].info[direct][0]

        elif check_dis+root.info[direct][1] < max(distances):
            check_dis+=root.info[direct][1]
            f_nodes[root.me].flag = True
            idx = root.info[direct][0]
        
        else:
            f_nodes[root.me].flag = True
            idx = root.info[direct][0]
            del_idx = f_del_idx(distances,check_dis)
            
            del distances[del_idx]
            check_dis =0
            need_friend+=1

    for i in f_nodes.values():
        if i.flag == False:
            return 1001
        
    return need_friend

def solution(n, weak, dist):
    answer = 101
    nodes = {}
    for i in range(len(weak)):
        if i == len(weak)-1:
            nodes[weak[i]] = Node(weak[i],weak[0],weak[i-1],n)
        else:
            nodes[weak[i]] = Node(weak[i],weak[i+1],weak[i-1],n)

    for i in nodes.keys():
        right = find_(i,deepcopy(nodes),deepcopy(dist),0)
        
        left = find_(i,deepcopy(nodes),deepcopy(dist),1)
        ans = min(right,left)
        answer = min(answer,ans)
       
    if answer >len(dist):
        return -1
    return answer