[프로그래머스] 도넛과 막대 그래프 - 258711(Java)

<문제>

• https://school.programmers.co.kr/learn/courses/30/lessons/258711
• 도넛 모양 그래프 : 크기 n, 정점 n개, 간선 n개
  • 아무 한 정점→이용한 적 없는 간선→나머지 n-1개의 정점들을 한 번씩 방문→원래 출발했던 정점

• 막대 모양 그래프 : 크기 n, 정점 n개, 간선 n-1개
  • 임의의 한 정점→간선 따라감→나머지 n-1개 정점 한번씩 방문

• 8자 모양 그래프 : 크기 n, 정점 2n+1개, 간선 2n+2개
  • 크기가 동일한 도넛 모양 그래프 2개에서 정점을 하나씩 골라 결합

⇒생성한 정점의 번호와 정점을 생성하기 전 도넛 모양 그래프의 수, 막대 모양 그래프의 수, 8자 모양 그래프의 수?

<입력>

• 2차원 정수 배열(edges) - 그래프의 간선 정보

<출력>

• 1차원 정수 배열 - [생성한 정점의 번호, 도넛 모양 그래프의 수, 막대 모양 그래프의 수, 8자 모양 그래프의 수] return

edges	result
[[2, 3], [4, 3], [1, 1], [2, 1]]	[2, 1, 1, 0]
[[4, 11], [1, 12], [8, 3], [12, 7], [4, 2], [7, 11], [4, 8], [9, 6], [10, 11], [6, 10], [3, 5], [11, 1], [5, 3], [11, 9], [3, 8]]	[4, 0, 1, 2]

<제한사항>

• 1 ≤ edges의 길이 ≤ 1,000,000
  • edges의 원소는 [a,b] 형태이며, a번 정점에서 b번 정점으로 향하는 간선이 있다는 것을 나타냅니다.
  • 1 ≤ a, b ≤ 1,000,000
• 문제의 조건에 맞는 그래프가 주어집니다.
• 도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프의 수의 합은 2이상입니다.

<풀이>

• 중심 정점과 그래프들의 특징
  • 중심 정점: 새롭게 만든 정점, 자기 자신으로부터 각각의 그래프를 연결, 최소 간선 개수는 2개, 나가는 간선만 존재
  • 막대 그래프: 나가는 간선X, 들어오는 간선 1개 이상
  • 8자 그래프: 나가는 간선 2개, 들어오는 간선 2개 이상
  • 도넛 그래프: 나가고 들어오는 간선 각각 1개씩, 정점노드 나가는 간선 수-막대 그래프 개수-8자 그래프 개수

<전체코드>

import java.util.*;
class Solution {
    public int[] solution(int[][] edges) {
        Map<Integer, int[]> nodeCount = new HashMap<>();
        int[] answer = {0,0,0,0};
        Arrays.stream(edges).forEach(edge -> {
            int a = edge[0];
            int b = edge[1];
            if(!nodeCount.containsKey(a))
                nodeCount.put(a, new int[]{0,0});
            if(!nodeCount.containsKey(b))
                nodeCount.put(b, new int[]{0,0});
            nodeCount.get(a)[0] += 1; //나가는 간선
            nodeCount.get(b)[1] += 1; //들어오는 간선
        });
        
        int[] count;
        for(int key : nodeCount.keySet()) {
            count = nodeCount.get(key);
            if(count[0]>=2 && count[1]==0) //정점
                answer[0] = key;
            else if(count[0]==0 && count[1]>0) //막대 그래프
                answer[2]++;
            else if(count[0]>=2 && count[1]>=2) //8자 그래프
                answer[3]++;
        }
        answer[1] = nodeCount.get(answer[0])[0] - answer[2] - answer[3]; //도넛 그래프
        return answer;
    }
}