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

 

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

프로그래머스

도넛과 막대 그래프 문제

그래프의 시작 정점, 도넛 그래프 수, 막대 그래프 수, 8자 그래프 수를 구하는 문제

 

#사용 알고리즘

구현

📌문제 접근 포인트

1. 각 그래프의 모양의 조건을 따져보자. 정점의 위치를 찾기 위해서는 정점은 그래프들과 무관하므로 들어오는 선은 없고 나가는 선만 2개 이상이면 시작점이다.

2. 막대 그래프는 나가는 선이 없지만 들어오는 선이 존재하는 정점이 size에 상관 없이 막대그래프의 끝 점이다. 즉, 이런 정점의 갯수 = 막대그래프의 수 이다.

3. 8자 모양 그래프는 들어오는 선이 2개 이상이고 나가는 선도 2개 이상인 정점이 size에 상관 없이 8자 모양 그래프의 중심점이다. 즉, 이런 정점의 갯수 = 8자 모양 그래프의 수 이다.

4. 도넛 모양 그래프는 전체 그래프 수 - 막대 그래프 수 - 8자 모양 그래프 수이다.

5. 위 조건에 맞게 분기하여 탐색하면 구현 성공

반응형

⚙ 내가 푼 정답 코드

class Solution {
    public int[] solution(int[][] edges) {
        int[] answer = new int[4];
        int[] in = new int[1000001];
        int[] out = new int[1000001]; 
        
        for (int[] edge : edges) {
            out[edge[0]]++; // 정점당 나가는 선 수
            in[edge[1]]++; // 정점당 들어오는 선 수
        }
        
        for (int i = 1; i < 1000001; i++) {
            // 들어오는 선이 없고 나가는 선이 2개 이상(모든 그래프 수의 합은 2이상)이면 시작 정점
            if (in[i] == 0 && out[i] > 1) {
                answer[0] = i;
            }
            // 나가는 선은 없고 들어오는 선이 1개 이상이면 막대 모양 그래프
            else if (out[i] == 0 && in[i] >= 1) {
                answer[2]++;
            }
            // 들어오는 선이 2개 이상이고 나가는 선도 2개 이상이면 8자 모양 그래프
            else if (in[i] >= 2 && out[i] >= 2) {
                answer[3]++;
            }
        }
        // 시작 정점의 나가는 선 수(전체 그래프 수)에서 다른 그래프들 수를 빼면 도넛 모양 그래프 수
        answer[1] = out[answer[0]] - answer[2] - answer[3];
        
        return answer;
    }
}