[Programmers] 도넛과 막대 그래프

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/258711

프로그래머스

문제 풀이

무관한 정점을 생성한 edges에서 무관한 정점과 도넛, 막대, 8자 모양 그래프의 개수를 구하기.

1. 무관한 정점 찾기 : 정점에 들어오는 간선 == 0 && 나가는 간선 > 1을 충족해야 함
(예시 1번)의 4번 정점과 같이 들어오는 간선은 없지만 나가는 간선이 1개인 것은 막대 그래프일 수도 있기 때문
        
2. 그래프 개수 세기 : 정점에서 나가는 간선이 없고 들어오는 간선이 1개 이상이면 막대 그래프, 나가는 간선이 2개 이상이면 8자 그래프이다. 모든 그래프는 무관한 정점과 이어져 있기 때문에 (무관한 정점에서 나가는 간선 = 도넛 + 막대 + 8자)이기 때문에 막대와 8자를 알면 도넛 그래프 개수도 구할 수 있다.

 

※ 문제에서 노드의 범위는 1_000_000이지만 혹시 몰라서 edge.length + 2까지 설정하니 시간은 줄일 수 있었다. 하지만 범위에 맞춰야 함.

코드

import java.util.*;

class Solution {

    int[] answer = new int[4];
    int MAX = 1_000_001;

    public int[] solution(int[][] edges) {
        // init       
        int[] inArr = new int[MAX];
        int[] outArr = new int[MAX];
        
        for(int[] edge : edges) {
            inArr[edge[1]]++;
            outArr[edge[0]]++;
        }
        
        // 무관한 정점 찾기
        answer[0] = findNode(inArr, outArr);
        
        // 그래프 모양 개수 구하기
        countGraph(inArr, outArr);
        
        answer[1] = outArr[answer[0]] - answer[2] - answer[3];
        return answer;
    }
    
    public int findNode(int[] inArr, int[] outArr) {        
        int node = 0;
        
        for(int i=1; i<MAX; i++) {
            if(inArr[i] == 0) {
                if(outArr[i] > 1) return i;
                node = i;
            } 
        }
        return node;
    }

    public void countGraph(int[] inArr, int[] outArr) {
        for(int i=1; i<MAX; i++) {
            if(i == answer[0]) continue;
            
            if(outArr[i] > 1) answer[3]++;
            else if(inArr[i] > 0 && outArr[i] == 0) answer[2]++;
        }
    } 
}