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

문제

https://school.programmers.co.kr/learn/courses/30/lessons/258711?language=java

프로그래머스

 

---

정리

어떻게 풀어야 할 지 감도 잡히지 않아서 다른 분들 풀이를 많이 참고했다. 정식 풀이 링크

갯수를 구해야 하는 그래프 모양은 3개다.

막대 / 8자 / 도넛 모양이다.

 

막대

나가는 간선은 2개 이상 존재하고 들어오는 간선은 존재하지 않는다. (도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프의 수의 합은 2이상 이라는 조건이 있음)

 

8자

나가는 간선이 2개 이상 존재하고 들어오는 간선도 2개 이상 존재한다. (8자의 중간 모양은 들어오는 것 2개 & 나가는 것 2개이상임, 나머지는 순환하기 때문에 1,1)

 

도넛

순환 기준 나가는 간선 1개, 들어오는 간선 1개지만, 

도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프가 여러 개 있습니다. 이 그래프들과 무관한 정점을 하나 생성한 뒤, 각 도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프의 임의의 정점 하나로 향하는 간선들을 연결했습니다.

 

위 조건에 의해

무관한 정점에 연결되어 있는 그래프 갯수 전체 개수 = 막대 그래프 개수 + 8자 그래프 개수 + 도넛 그래프 개수

 

가 성립하게 되고 

도넛 그래프 개수 = 무관한 정점에 연결되어 있는 그래프 갯수 전체 개수 - 막대 그래프 개수 - 8자 그래프 개수

 

로 도넛 그래프 개수를 구할 수 있게 된다.

---

풀이

import java.util.*;

class Solution {
    public int[] solution(int[][] edges) {
        int[] answer = new int[4];
        /* edge, [enterCnt, leaveCnt] */ 
        Map<Integer, int[]> map = new HashMap<>();
        for (int i=0; i<edges.length; i++) {
            int[] edge = edges[i];
            int leaveEdge = edge[0];
            int[] leaveEdgeCnts = map.getOrDefault(leaveEdge, new int[2]);
            leaveEdgeCnts[1]++; // increase leaveCnt
            map.put(leaveEdge, leaveEdgeCnts);
            
            int enterEdge = edge[1];
            int[] enterEdgeCnts = map.getOrDefault(enterEdge, new int[2]);
            enterEdgeCnts[0]++; // increase enterCnt
            map.put(enterEdge, enterEdgeCnts);
        }
        
        map.forEach((edge, leaveEnterCnts) -> {
            int leaveCnt = leaveEnterCnts[1];
            int enterCnt = leaveEnterCnts[0];
            if (enterCnt == 0 && leaveCnt > 1) {
                answer[0] = edge;
                return;
            }
            
            // 막대모양 개수
            if (enterCnt > 0 && leaveCnt == 0) {
                answer[2]++;
                return;
            }
            
            // 8자모양 개수
            if (enterCnt > 1 && leaveCnt > 1) {
                answer[3]++;
                return;
            }
        });
        
        // 이 그래프들과 무관한 정점을 하나 생성한 뒤, 각 도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프의 임의의 정점 하나로 향하는 간선들을 연결 -> 막대 모양과 8자 모양 갯수를 제외하면 도넛 모양 개수가 나온다.
        answer[1] = map.get(answer[0])[1] - answer[2] - answer[3];
        return answer;
    }
}import java.util.*;

class Solution {
    public int[] solution(int[][] edges) {
        int[] answer = new int[4];
        /* edge, [enterCnt, leaveCnt] */ 
        Map<Integer, int[]> map = new HashMap<>();
        for (int i=0; i<edges.length; i++) {
            int[] edge = edges[i];
            int leaveEdge = edge[0];
            int[] leaveEdgeCnts = map.getOrDefault(leaveEdge, new int[2]);
            leaveEdgeCnts[1]++; // increase leaveCnt
            map.put(leaveEdge, leaveEdgeCnts);
            
            int enterEdge = edge[1];
            int[] enterEdgeCnts = map.getOrDefault(enterEdge, new int[2]);
            enterEdgeCnts[0]++; // increase enterCnt
            map.put(enterEdge, enterEdgeCnts);
        }
        
        map.forEach((edge, leaveEnterCnts) -> {
            int leaveCnt = leaveEnterCnts[1];
            int enterCnt = leaveEnterCnts[0];
            if (enterCnt == 0 && leaveCnt > 1) {
                answer[0] = edge;
                return;
            }
            
            // 막대모양 개수
            if (enterCnt > 0 && leaveCnt == 0) {
                answer[2]++;
                return;
            }
            
            // 8자모양 개수
            if (enterCnt > 1 && leaveCnt > 1) {
                answer[3]++;
                return;
            }
        });
        
        // 이 그래프들과 무관한 정점을 하나 생성한 뒤, 각 도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프의 임의의 정점 하나로 향하는 간선들을 연결 -> 막대 모양과 8자 모양 갯수를 제외하면 도넛 모양 개수가 나온다.
        answer[1] = map.get(answer[0])[1] - answer[2] - answer[3];
        return answer;
    }
}