[Java | Algorithm] 프로그래머스 Lv2 - 도넛과 막대 그래프

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

프로그래머스

1) 문제 설명

2) 접근 방식

처음엔 그래프 탐색으로 풀어야겠지 생각했다가 규칙이 있을 거 같아서 규칙 찾는 데 오래 고민했던 문제입니다.

규칙

1. 생성된 정점: 나가는 간선(out)이 2개 이상 존재하고 들어오는 간선(in)이 존재하지 않습니다.
2. 막대 모양 그래프: 마지막 정점은 나가는 간선(out)이 없습니다.
3. 도넛 모양 그래프: 모든 정점이 나가는 간선(out)과 들어오는 간선(in)이 하나씩 존재합니다.
4. 8자 모양 그래프: 1개의 정점은 나가는 간선(out) 2개와, 들어오는 간선 2개가 존재합니다.

3) 풀이

전체 코드입니다.

import java.util.*;

class Solution {
    public int[] solution(int[][] edges) {        
        // 각 정점의 in-degree와 out-degree를 저장하기 위한 맵 생성
        HashMap<Integer, Integer> in = new HashMap<>();   // in-degree를 저장하는 맵
        HashMap<Integer, Integer> out = new HashMap<>();  // out-degree를 저장하는 맵
        
        // 결과를 저장할 배열 선언. [생성된 정점 번호, 도넛 모양 그래프 수, 막대 모양 그래프 수, 8자 모양 그래프 수]
        int[] answer = new int[4];
        
        // 각 간선을 순회하며 in-degree와 out-degree를 업데이트
        for (int[] edge : edges) {
            out.put(edge[0], out.getOrDefault(edge[0], 0) + 1); // 출발 정점의 out-degree 증가
            in.put(edge[1], in.getOrDefault(edge[1], 0) + 1);   // 도착 정점의 in-degree 증가
        }
        
        // out-degree가 2 이상이고, in-degree가 없는 경우를 탐색
        // 이 정점은 새로 생성된 정점일 가능성이 높음
        for (int node : out.keySet()) {
            if (out.get(node) > 1) { // out-degree가 1보다 큰 경우
                if (!in.containsKey(node)) { // in-degree가 0인 경우
                    answer[0] = node; // 생성된 정점 번호로 설정
                } else {
                    answer[3] += 1; // in-degree가 있으면 8자 모양 그래프 수 증가
                }
            }
        }
        
        // out-degree가 없는 노드를 찾음
        // 막대 모양 그래프의 끝 정점을 찾아 막대 모양 그래프 수를 계산
        for (int node : in.keySet()) {
            if (!out.containsKey(node)) { // out-degree가 없는 경우
                answer[2] += 1; // 막대 모양 그래프 수 증가
            }
        }
        
        // 도넛 모양 그래프의 수는 총 연결된 그래프 수에서 막대 모양과 8자 모양 그래프 수를 뺀 값
        answer[1] = out.get(answer[0]) - answer[2] - answer[3];
        
        return answer; // 결과 반환
    }
}

정리

어려웠지만 나름 규칙 찾는 재미가 있었던 문제입니다.
최근에 프로젝트 하느라 알고리즘을 풀 지 못했는데 더 열심히 풀어야겠습니다!!