[프로그래머스][Python] 2023 KAKAO BLIND RECRUITMENT : 1,2,3 떨어트리기

1일 1PS 34일차!

📚 문제

---

Lv 4

• 처음부터 어떤 숫자를 떨어트릴 지 정할 수 없다.
• 몇 개의 숫자가 떨어질 지 정한 후 이를 통해 어떤 숫자를 떨어트렸는 지 파악한다.

💡 풀이과정

---

1. 단방향 graph 를 저장하고 각 노드들이 현재 가르키고 있는 graph_path 를 배열로 저장한다.
2. root 노드부터 graph 를 따라 이동하며 해당 node 를 이동할 때 graph_path 를 +1 한다. 당연히 마지막에 도달하면 0으로 돌아간다.
3. child 가 없는 노드라면 count 에 저장하고 모든 count 수만큼 1, 2, 3 을 조합해서 목표값이 만들어진다면 루프문을 멈춘다.
4. current_node 로 노드에 떨어진 순서를 저장하고 각 모든 노드의 1, 2, 3 조합을 사전 순서대로 구한다.
5. current_node 를 각 노드에서 조합한 1, 2, 3 으로 교체해 출력한다.

💻 코드

---

def solution(edges, target):
    answer = []

    l = len(target)

    graph = [[] for _ in range(l + 1)]
    graph_path = [0 for _ in range(l + 1)]
    count = [0 for _ in range(l + 1)]


    for edge in edges:
        graph[edge[0]].append(edge[1])
    for g in graph:
        g.sort()

    flag = True

    while flag:
        current_node = 1
        while graph[current_node]:
            post_node = current_node
            current_node = graph[current_node][graph_path[current_node]]
            graph_path[post_node] = (graph_path[post_node]+1) % len(graph[post_node])
        count[current_node] += 1
        answer.append(current_node)

        flag2 = True
        for i in range(len(target)):
            cnt = count[i + 1]
            if not (cnt * 1 <= target[i] <= cnt * 3):
                flag2 = False
            if target[i] < cnt:
                return [-1]

        if flag2:
            flag = False

    num_list = [[] for _ in range(l)]
    for i in range(len(target)):
        cnt = count[i + 1]
        num_list[i] = [1] * cnt
        target_num = target[i] - cnt
        for j in range(cnt):
            if target_num >= 2:
                num_list[i][j] = 3
                target_num -= 2
            elif target_num == 1:
                num_list[i][j] = 2
                target_num -= 1
            else:
                break

    result = []
    for an in answer:
        result.append(num_list[an - 1].pop())
    return result