프로그래머스 (카카오 기출) | LV.2 도넛과 막대 그래프 - Graph 문풀 (Java)

⬛ 프로그래머스 (카카오 기출) | LV.2 도넛과 막대 그래프 - 그래프 문풀

2024 카카오 winter intership 기출 

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

프로그래머스

문제 설명 1

문제 설명2

제한 사항

---

💚문제 접근 방식

 세 가지 모양의 그래프와 생성된 정점의 특징을 분석하는 것이 핵심인 문제

풀이 설명

[한 눈에 정리하면 다음과 같다]

1) 생성된 정점 : 진입 X, 진출 2개 이상

2) 도넛 그래프 개수 : 규칙성 명확하진 않으니 전체 그래프 개수 - (도넛&막대) 제거 개수

3) 막대 그래프 개수 : 막대 형성 마지막 정점 특징 (진입 1개, 진출 0개) 갖는 정점 카운팅

4) 8자 그래프 개수 : 8자의 중심 정점 특징 (진입 2개이상, 진출 2개 이상)

HashMap에 담긴 Key, value(진출, 진입)차수 출력한 모습

예제 케이스 풀이 설명

[코드 풀이 방식]

데이터가 100만개라서 이왕이면 그래프 전체를 순회하며 특징을 확인하는 것보다 간선 정보의 (진입, 진출 차수) 데이터만 가지고 분리시켜서 접근하는 게 낫다.

1) HashMap에 key=정점 , value 에는 int[]배열 담아서 (진출차수, 진입차수)를 담는다.

2) map 을 순회하면서, 각 정점에 대한 진입차수 진출차수를 각 그래프 규칙성에 맞게 분류하여 그래프 개수들을 세팅했다.

• 막대 그래프를 형성하는 마지막 정점 특성 (진출 0개) 이용하여 마지막 정점 개수++처리
• 8자 그래프를 형성하는 중심 정점 (진입과 진출 모두 2개 이상) 이용하여 ++처리
• 생성된 정점은 진입 X, 진출 2개 이상인 (그래프 덩어리 잇는 애) 이므로 답 세팅
• 도넛 그래프는 전체 그래프 개수 - (막대+8자) 값으로 구한다.

💚 제출 코드

import java.util.*;

class Solution {
    //솔루션 함수 
    public int[] solution(int[][] edges) {
        int[] answer = new int[4];
        Map<Integer, int[]> count = new HashMap<>(); //정점번호, (진출차수, 진입차수)
        
        for(int[] x : edges){
            int a = x[0];
            int b = x[1];
            //a->b 순의 방향 간선 
            if(!count.containsKey(a)){//기존에 없는 정점이라면 
                count.put(a, new int[] {0, 0});
            }
            if(!count.containsKey(b)){
                count.put(b, new int[] {0, 0});
            }
            
            count.get(a)[0]++; //a 진출차수 개수 ++처리
            count.get(b)[1]++; //b 진입차수 개수 ++처리
        }
        
        //순회하며 정점의 진출, 진입 가선  수 체크하며 판별
        for(int key : count.keySet()){
            int[] cur = count.get(key);//현재 정점의 차수 정보 배열 cur
            int in = cur[1]; //cur 진입차수
            int out = cur[0]; //cur 진출차수
                          
            if(in == 0 && out >= 2){ //생성된 정점 : 진입X, 진출2개 이상임
                answer[0] = key;//정점 번호 담기 
            }else if(in > 0 && out == 0){
                //막대 그래프
                answer[2]++;
            }else if(in >= 2 && out>=2){
                //8자 그래프
                answer[3]++;
            }
        }
                          
        //도넛 그래프
        answer[1] = count.get(answer[0])[0] - answer[2] - answer[3];
        
        
        return answer;
    }
}