[2024 KAKAO WINTER INTERNSHIP] 도넛과 막대 그래프

Problem details

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

프로그래머스

 

Ideas

1. 들어오는 선 없이 나오는 선이 2개 이상인 점이 정점이다.
2. 정점에서 나오는 선의 갯수가 전체 그래프의 수이다.
3. 정점과 정점에 연결된 선을 지우고 나서, 연결된 선이 없거나 들어오는 선이 하나고 나오는 선이 없는 정점의 갯수가 막대 모양 그래프의 갯수이다.
4. 정점과 정점에 연결된 선을 지우고 나서, 나오는 선이 2개인 정점의 갯수가 8자 모양 그래프의 갯수이다.
5. 전체 그래프의 수에서 막대 모양 그래프의 갯수와 8자 모양 그래프의 갯수를 빼면 도넛 모양 그래프의 갯수이다.

 

Answer code (Java)

class Solution {
    public int[] solution(int[][] edges) {

        // 배열 생성
        int[] shootCnt = new int[1000000 + 1];
        int[] receiveCnt = new int[1000000 + 1];
        for (int i = 0; i < edges.length; i++) {
            shootCnt[edges[i][0]]++;
            receiveCnt[edges[i][1]]++;
        }
        // 사용하지 않는 점 제거
        for (int i = 1; i <= 1000000; i++) {
            if (shootCnt[i] == 0 && receiveCnt[i] == 0) {
                shootCnt[i] = -1;
                receiveCnt[i] = -1;
            }
        }
        
        // 정점 찾기
        int totalGraphsNum = 0;
        int point = 0;
        for (int i = 1; i <= 1000000; i++) {
        	// Idea1 : 들어오는 선 없이 나오는 선이 2개 이상인 점이 정점이다.
            if (shootCnt[i] >= 2 && receiveCnt[i] == 0) {
                point = i;
                // Idea2 : 정점에서 나오는 선의 갯수가 전체 그래프의 수이다.
                totalGraphsNum = shootCnt[point];
            }
        }
        // 정점 제거
        shootCnt[point] = -1;
        receiveCnt[point] = -1;
        
        // 정점과 연결된 선 제거
        for (int i = 0; i < edges.length; i++) {
            if (edges[i][0] == point || edges[i][1] == point) {
                shootCnt[edges[i][0]]--;
                receiveCnt[edges[i][1]]--;

                edges[i][0] = 0;
                edges[i][1] = 0;
            }
        }
        
        int stickGraphsNum = 0;
        int eightGraphsNum = 0;
        for (int i = 1; i <= 1000000; i++) {
            // Idea3 : 정점과 정점에 연결된 선을 지우고 나서, 연결된 선이 없거나 들어오는 선이 하나고 나오는 선이 없는 정점의 갯수가 막대 모양 그래프의 갯수이다.
            if ((shootCnt[i] == 0 && receiveCnt[i] == 0) || 
                (shootCnt[i] == 0 && receiveCnt[i] == 1)) {
                stickGraphsNum++;
            }
            
            // Idea4 : 정점과 정점에 연결된 선을 지우고 나서, 나오는 선이 2개인 정점의 갯수가 8자 모양 그래프의 갯수이다.
            if (shootCnt[i] == 2) {
                eightGraphsNum++;
            }
        }
        // Idea5 : 전체 그래프의 수에서 막대 모양 그래프의 갯수와 8자 모양 그래프의 갯수를 빼면 도넛 모양 그래프의 갯수이다.
        int doughnutGraphsNum = totalGraphsNum - stickGraphsNum - eightGraphsNum;
        
        int[] answer = {point, doughnutGraphsNum, stickGraphsNum, eightGraphsNum};
        return answer;
    }
}