<Lv.3> 1,2,3 떨어트리기 (프로그래머스 : C#)

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

📕 문제 설명

트리의 1번 노드에 1,2,3 중 하나씩 떨어트려 리프 노드에 숫자를 쌓을 때 가장 적은 숫자를 사용하여 target 만들 수 있는 경우 반환하기

모든 부모 노드는 자식 노드와 연결된 간선 중 하나의 길로 설정하며 가장 번호가 작은 노드를 가리키는 간선을 초기 길로 설정 (숫자가 지나간 후에는 다음으로 큰 번호로 길 변경)

• Input
  트리 각 노드들 연결 관계, 각 노드별로 만들어야 하는 숫자 합 담은 정수 배열
• Output
  가장 적은 숫자를 사용하여 target 만들 수 있는 경우 (그 중 사전순으로 가장 빠른 경우)

예제

풀이

1. 루트에서 리프 노드로 타고 가면서 숫자 개수 얼마나 쌓이는지 저장 (이때, 현재 보고 있는 leaf node를 리스트에 저장해둔다.)

(현재 노드를 지난 횟수 % 자식 노드 개수)으로 가야할 간선 방향 (즉, 다음 방문할 자식 노드) 결정

ex) 부모 = 1번 노드, 자식 = 2번, 3번 노드
현재 부모 노드를 3번 지나는 차례라면 (2번 -> 3번 -> 2번), 2번의 방문 차례가 된다.

최대값(3) * 떨어진 개수가 target 보다 크거나 같아진다면 해당 노드는 현재 개수로 target 만들기 가능한 상태 => 방문처리

이런식으로 leaf 중 target이 존재하는 노드드에 대해 방문이 끝나면 종료

2. 리프 노드에 쌓이는 숫자 개수가 모두 정해지면 이전에 저장해둔 방문 순서대로 저장된 리프 노드들을 순회한다. 순회하면서 1~3까지 (사전순 조건) 조건을 만족하면 답에 해당 값을 붙여준다.

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public int[] solution(int[,] edges, int[] target) {
        int n = edges.GetLength(0) + 1;
        List<int>[] tree = new List<int>[n];
        List<int> leafNodes = new List<int>();

        int[] pass = new int[n]; // 노드 지난 횟수
        int[] cnt = new int[n]; // 리프 노드에 떨어진 숫자 개수
        bool[] visited = new bool[n]; // 체크한 노드인지 저장
        
        // tree 초기화
        for (int i = 0; i < n; i++) tree[i] = new List<int>();
        for (int i = 0; i < edges.GetLength(0); i++) tree[edges[i, 0] - 1].Add(edges[i, 1] - 1);
        for (int i = 0;i < n; i++) tree[i].Sort(); // 노드 번호 낮은 순 정렬
        
        int T = 0;
        // 리프노드 + target 떨어뜨려야하는 수 
        for (int i = 0;i < n;i++) if (tree[i].Count == 0 && target[i] > 0) T++;
        // 케이스 실행
        while (T > 0) 
        {
            int node = 0; // 루트에서 떨어트리기 시작

            // 리프 노드까지 떨어트리기
            while (tree[node].Count > 0) 
            {
                // 현재 노드 다음 간선 방향 설정
                node = tree[node][pass[node]++ % tree[node].Count];
            }
            // 리프 노드에 떨어진 숫자 개수 증가
            cnt[node] += 1;
            // 현재 방문한 리프노드 저장
            leafNodes.Add(node);

            // 현재 노드가 보유하고 있는 숫자 개수가 target보다 크면 target만들기 불가능
            if (cnt[node] > target[node]) return new int[1] {-1} ;

            // 최대값이 target보다 커지면 => target 만들기 가능한 케이스
            if (!visited[node] && target[node] <= 3 * cnt[node])
            {
                // 현재 보고있는 리프 방문 표시
                visited[node] = true;
                T--; // 다음 리프 노드 케이스로 
            }
        }
        
        List<int> res = new List<int>();
        // 방문 순서대로 담겨있는 leafnode => 사전순으로 value 보면서 결과 저장
        foreach (int leafNode in leafNodes) 
        {
            cnt[leafNode] -= 1;
            for (int val = 1; val <= 3; val++) 
            {
                // val = 대입한 수, target - val => 조건 만족 필요
                if (cnt[leafNode] <= target[leafNode] - val && target[leafNode] - val <= 3 * cnt[leafNode]) 
                {
                    res.Add(val);
                    target[leafNode] -= val;
                    break;
                }
            }
        }
        
        int[] answer = new int[res.Count];
        for (int i = 0; i < res.Count; i++) answer[i] = res[i];
        return answer;
    }

}

결과