[프로그래머스] 도넛과 막대 그래프 (JAVA)

[풀이]

먼저 각 그래프의 특징을 파악하면 된다.

막대 그래프

막대 그래프의 경우 다른 그래프에서는 존재하지 않는 

나가는 간선이 없고 들어오는 간선은 1개 이상인 정점이 한개 존재한다.

 

size가 1인 경우에도 새로 추가한 정점으로부터 나온 간선이 들어오기 때문에 

들어오는 간선은 무조건 1개 이상 존재하게 된다.

 

 

8자 그래프

8자 그래프의 경우는 나가는 간선 2개 그리고 들어오는 간선이 2개

따라서 총 4개의 간선이 존재하는 정점 한개가 존재한다.

 

8자 그래프

사실 8자 그래프의 경우, 8자 그래프에만 존재하는 특징을 따로 찾을 수 없었다.

 

하지만 다행히 문제에서 기존의 그래프가 존재하는 상황에서 이 그래프와 무관한 정점을 하나 추가하고, 

정점에서 각 그래프로 향하는 간선들을 연결했다.

이 말에 의하면 새로 추가한 정점의 나가는 간선 수가 총 그래프의 개수가 된다.

따라서 8자 그래프의 개수 = 새로 추가한 정점의 나가는 간선 개수 - (도넛 그래프 수 + 막대 그래프 수) 가 된다.

 

또한 문제 제한 사항에서 아래와 같이 주어졌기 때문에

도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프의 수의 합은 2이상입니다.

정점 중에서 나가는 간선만 2개 이상 존재하고, 들어오는 간선이 없는 정점을 발견한다면 해당 정점이 새로 추가한 정점이 된다.

그리고 해당 정점의 나가는 간선 개수가 전체 그래프 개수가 되는 것이다.

 

위의 정보들을 기반으로 코드를 구현했다.

나가는 간선, 들어오는 간선 정보를 저장하기 위해 output, input 배열을 선언했다.

edges 정보를 기반으로 각 정점별 output, input 간선들을 count 했다.

 

그리고 각 정점들의 input, output 간선들의 개수를 기반으로 

8자 그래프 , 막대 그래프, 새로 추가된 정점의 번호를 알 수 있었다.

 

이를 기반으로

새로 추가한 정점의 나가는 간선 개수 - (도넛 그래프 수 + 막대 그래프 수)  값을 계산하여 도넛 그래프의 개수도 알 수 있었다.

 

[코드]

class Solution {
    static final int MAX = 1_000_000;

    public int[] solution(int[][] edges) {
        int MAX_IDX =0;
        int[] input, output;

        input = new int[MAX+1];
        output = new int[MAX+1];

        for(int[] edge : edges) {
            output[edge[0]]++;
            input[edge[1]]++;
            MAX_IDX = Math.max(MAX_IDX, Math.max(edge[0],edge[1]));
        }

        int totalGraph = 0;
        // 각 그래프 개수
        int stickGraph = 0;
        int donutGraph = 0;
        int eightGraph = 0;
        // 새로 추가된 노드 번호
        int edgeIdx = 0;
        for(int idx = 1; idx<= MAX_IDX; idx++) {
            if(input[idx] >= 2 && output[idx] >= 2) eightGraph++;
            else if(output[idx] == 0 && input[idx] > 0)   stickGraph++;
            else if(output[idx] >= 2 && input[idx] == 0) {
                edgeIdx = idx;
                totalGraph=output[idx];
            }
        }
        donutGraph =totalGraph-(eightGraph+stickGraph);
        int[] answer = {edgeIdx, donutGraph, stickGraph, eightGraph};
        return answer;
    }
}

[문제]

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

프로그래머스