[프로그래머스] 1,2,3 떨어트리기 - 파이썬

2023 KAKAO BLIND RECRUITMENT - 150364. 1,2,3 떨어트리기

[Lv. 4]

 

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

프로그래머스

 

풀이

문제를 읽고 처음에는, DFS - Backtracking 문제인가? 생각했음.

일단, 완전히 뇌 빼고 Brute-Force로 풀어내기에는 3^100 이니까 될 수가 없고,

그런데 생각해보니까 Backtracking으로 간다고 해도 [1,1,1, ...] 부터 쭉 시작하는 거니까, complexity가 상당히 커질 것 같다는 생각이... 듬.

 

그리고, target대로 숫자의 합을 만들 수 없는 경우 [-1] 을 출력하라는 부분에서,

'그럼 숫자의 합을 만들 수 있는 경우와 없는 경우를 먼저 구분할 수 있을 것 같은데, 어떻게 할까..'

라는 생각을 했고, 그 경우를 생각하다 보니,

'결국 사이클이 돌고, (숫자를 넣을 때마다 숫자가 들어가는 리프 노드가 정해져 있으며,) 넣을 수 있는 숫자는 1~3뿐이니, 어떤 리프 노드에 도달하는 횟수가 다른 리프 노드에 도달하는 횟수의 대충 3~4배보다 넘어가거나 하면 불가능하겠구나!' 라는 생각에 도달했다.

 

---

 

그럼 우선, '리프 노드 도달 횟수' 만을 로직에 따라 계산해서 저장할 수 있다.

문제 예시를 예로 들면, 아래와 같이 리프 노드에 숫자를 떨어뜨리게 된다.

4, 8, 7, 9, 4, 10, 7, 8, 4, 9, 7, 10, // 4, 8, 7, 9, ....

[4, 7, 8, 9, 10] 번째 노드에 떨어뜨려야 하는 숫자의 총 합은(target은)

[3, 5, 1, 2, 3] 이므로, 허용되는 리프 노드 방문 횟수는 [1~3, 2~5, 1, 1~2, 1~3] 이다.

[(target 수) / 3 의 소숫점 올림] 회 ~ [(target 수)]회 까지가 허용되는 리프 노드 방문 횟수.

(1~3을 떨어트릴 수 있으므로.)

로직에 따라 방문하며 횟수를 기록하면서, 허용되는 리프 노드 방문 횟수를 모두 만족할 때 반복을 종료한다.

만약 허용되는 횟수를 초과한 순간, -1을 출력하면 된다.

이 방식으로 우선 '리프 노드 도달 횟수'를 계산한다.

 

---

 

그 후는, '사전 순으로 가장 빠른 해답'을 찾아야 하기 때문에, 최대한 1을 앞에 많이 배치시키는 형식으로 만들어야 한다.

따라서, 뒤에서부터 최대한 큰 숫자 (3)을 넣어 주면 되는데, 1, 2, 3중에서 계산하면, 3을 무작정 많이 넣기는 앞쪽에 1을 넣어야 하므로 불가능하다.

ex) 리프 노드 도달 순서가 [2, 3, 2, 3, 2]이고, target이 {2: 6, 3: 3}이면, 뒤에서부터 숫자를 채워 나갈 때, 무작정 3부터 채우다가는 [0, 0, 3, 3, 3] 꼴이 되어 버린다. 0을 떨어트릴 수는 없으므로, 이렇게 하면 앞에 남아있는 같은 리프 노드의 개수를 세면서 나아가야 함.

 

따라서, 모든 곳에 1을 우선적으로 채워 넣고, 선택지를 0, 1, 2로 바꾼다면, 맨 뒤에서부터 가능한 만큼 숫자를 계속 채워 나가면 될 것이다.

ex) 똑같이, 리프 노드 도달 순서가 [2, 3, 2, 3, 2]이고, target이 {2: 6, 3: 3}이면, result : [1, 1, 1, 1, 1] 처럼 미리 채워 놓은 후, [1, 1, 1, 1, 1] -> [1, 1, 1, 1, 3] -> [1, 1, 1, 2, 3] -> [1, 1, 2, 2, 3] 과 같이 뒤에서부터 채워 나갈 수 있다.

 

---

 

잠깐 고민했던 부분은, '리프 노드 도달 횟수'를 계산하기 위한 반복문을 빠져나올 때, Brute-Force로 리스트의 모든 원소에 대해 계산하면서 나아가도 되는가- 였는데, 생각해보니 edge의 수가 100개를 넘지 않으므로, 많아 봐야 100x100회라 그냥 전체 탐색으로 구현했다.

 

import math

def solution(edges, target):
    # graph 초기화
    graph = {i: [] for i in range(1, len(target)+1)}

    # graph 생성
    for edge in edges:
        v1, v2 = edge
        graph[v1].append(v2)

    # 리프 노드에 숫자가 떨어진 횟수 저장.
    leaf_cnt = {}
    # graph 내부 간선 정리, 리프 노드의 target 저장.
    for i in graph:
        if len(graph[i]) == 0:
            leaf_cnt[i] = 0
            continue
        graph[i] = sorted(graph[i])


    # cursor 초기화 (cursor -> 가리키는 child node의 index.)
    cursor = {i: -1 for i in range(1, len(target)+1)}
    for i in graph:
        if len(graph[i]):
            cursor[i] = 0

    # 리프 노드에 숫자가 떨어지는 순서.
    leaf = []

    # while문 flag값.
    isFin = False

    while not isFin:
        # root node에서 시작
        a = 1
        # 리프 노드에 도달할 때 까지 반복
        while cursor[a] != -1:
            temp = a
            a = graph[a][cursor[a]]
            # 지나간 후 커서를 새로 설정
            # 뒤에 길을 바꿀 child node가 남아있다면, cursor를 한 칸 옮김.
            if len(graph[temp]) > cursor[temp]+1:
                cursor[temp] += 1
            else:
                # 남아있지 않다면, 처음으로 돌아감.
                cursor[temp] = 0

        # 떨어뜨린 리프 노드의 순서 저장
        leaf.append(a)
        # 리프 노드의 떨어뜨려진 횟수 추가
        leaf_cnt[a] += 1
        # 만족하는 지 검증 (이 부분을 Brute-Force로 처리해도 되는 지 고민했으나, 최대 횟수가 100x100회를 넘지 않기 때문에, 전체 탐색으로 구현함.)
        isFin = True
        for i in leaf_cnt:
            if leaf_cnt[i] < int(math.ceil(target[i-1]/3)):
                isFin = False
                break
            elif leaf_cnt[i] > target[i-1]:
                # 허용 범위를 넘어가면.. -1 출력 후 종료
                return [-1]

    # ====================

    # 1 먼저 채워 넣기
    result = [1 for _ in range(len(leaf))]
    for i in leaf:
        target[i-1] -= 1

    # 뒤에서부터 되는 대로 숫자 추가하기 (0, 1, 2 중..)
    for i in range(len(leaf)-1, -1, -1):
        if target[leaf[i]-1] >= 2:
            result[i] += 2
            target[leaf[i]-1] -= 2
        elif target[leaf[i]-1] == 1:
            result[i] += 1
            target[leaf[i]-1] -= 1
        else:
            continue
            
    return result