[programmers] 도넛과 막대 그래프

21 May 2023 in Algorithm on Algorithm

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

import java.util.*;

class Solution {
    public int[] solution(int[][] edges) {
        Map<Integer, Integer> out = new HashMap<>();
        Map<Integer, Integer> in = new HashMap<>();
        int[] answer = new int[4];

        for (int[] edge : edges) { // in, out 간선 저장.
            out.put(edge[0], out.getOrDefault(edge[0], 0) + 1);
            in.put(edge[1], in.getOrDefault(edge[1], 0) + 1);
        }

        for (int node : out.keySet()) {
            if (out.get(node) > 1) { // [8자 그래프] out 간선 개수가 2개 이상인 정점 중에서 in 간선이 없으면 생성한 정점이고, 있으면 8자 그래프이다.
                if (!in.containsKey(node)) {
                    answer[0] = node;
                } else {
                    answer[3] += 1;
                }
            }
        }

        for (int node : in.keySet()) {
            if (!out.containsKey(node)) { // [막대 그래프] in 간선이 있는 정점 중에서 out 간선이 없으면 막대 그래프이다.
                answer[2] += 1;
            }
        }
        answer[1] = out.get(answer[0]) - answer[2] - answer[3]; // [도넛 그래프] 생성한 정점의 out 간선 개수 - 막대 그래프 개수 - 8자 그래프 개수이다.
        return answer;
    }
}