[프로그래머스] LV2. 도넛과 막대 그래프

💡 풀이

🫥 문제가 어려워서 다른 사람 풀이 참고했는데 생각보다 쉬웠던 문제

• 생성된 정점과 각 그래프의 특징을 찾으면 되는 문제
• 생성된 정점 : in은 무조건 0, out은 2개 이상
• 막대 모양 그래프 : out이 0인 정점이 있음 (마지막 정점)
• 8자 모양 그래프 : out이 2개 이상인 정점중에 in이 존재하는 정점
• 도넛 모양 그래프 : 생성된 정점의 out 간선 수 - 막대 그래프 - 8자 그래프
• 각 정점의 in과 out 간선 수를 각각 hashMap에 넣고 조건에 맞게 생성된 정점과 그래프 수 찾으면 됨

import java.util.*;

class Solution {
    public int[] solution(int[][] edges) {
        int[] result = new int[4];
        HashMap<Integer, Integer> in = new HashMap<>();
        HashMap<Integer, Integer> out = new HashMap<>();
        
        // 각 정점마다 in 간선과 out 간선 count 
        for(int[] edge : edges){ // a -> b
            int a = edge[0];
            int b = edge[1];
            in.put(b, in.getOrDefault(b, 0) + 1);
            out.put(a, out.getOrDefault(a, 0) + 1);
        }
        
        
        for(int o : out.keySet()){
            if (out.get(o) >= 2){
            	// 생성된 정점 찾기
                if (!in.containsKey(o)){
                    result[0] = o;
                 } else { // 8자 모양 그래프 찾기
                    result[3] += 1;
                }
            }
            
        }
        // 막대 모양 그래프 찾기
        for(int i : in.keySet()){
            if (!out.containsKey(i)) result[2] += 1;
        }
        
        result[1] = out.get(result[0]) - result[2] - result[3];
        
        return result;
    }
}