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

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

프로그래머스

 

특정 알고리즘을 사용할 필요는 없고, 문제의 이해와 해석이 요구되는 문제였다.  각 그래프의 특징을 생각하고, 이를 기반으로 각 그래프의 갯수를 구하면 된다. 각 그래프의 특징은 다음과 같다.

• 추가된 정점: 나가는 선이 2개 이상이면서 들어오는 선이 없다. 그리고 추가된 정점에서 나가는 선의 개수가 총 그래프의 갯수이다.
• 8자 모양 그래프: 나가는 선이 2개 이상이다.
• 막대 모양 그래프: 나가는 선이 없다. 

그리고 도넛 모양 그래프의 갯수는 총 그래프의 갯수 - (8자 모양 그래프의 수 + 막대 모양 그래프의 수)가 된다.

 

주의할 점은 위에서 정의한 특징들에 반례가 없는지를 잘 살펴야 한다. 특히 정점으로부터 각 그래프로 선이 이어지기 때문에, 각 그래프로 들어오는 선의 갯수가 아닌 나가는 선의 갯수를 기준으로 보는 것이 좋다. (예를 들어, 8자 모양 그래프는 나가는 선이 2개이면서 들어오는 선이 2개인데, 추가된 정점이 8자 모양 그래프에 선을 그으면서 들어오는 선이 3개가 될 수도 있다.)

 

위 특징에 맞게 코드로 구현하면 다음과 같다.

        // 정점: 나가는 선이 2개 이상 + 들어오는 선 없음
        int node = 0;
        for (int i = 1; i <= max; i++) {
            if (out.get(i).size() >= 2 && in.get(i).size() == 0) {
                node = i;
                break;
            }
        }
        int totalCnt = out.get(node).size();
        
        // 8자: 나가는 선 2개
        int eight = 0;
        for (int i = 1; i <= max; i++) {
            if (i == node) continue;
            if (out.get(i).size() == 2) {
                eight++;
            }
        }
        
        // 막대: 나가는 선 없음
        int bar = 0;
        for (int i = 1; i <= max; i++) {
            if (i == node) continue;
            if (out.get(i).size() == 0) {
                bar++;
            }
        }
        
        // 생성한 정점 번호, 도넛 수, 막대 수, 8자 수 반환
        return new int[]{node, totalCnt - (bar + eight), bar, eight};

 

그런데 마지막 테스트 케이스에서 틀렸다. 그 이유는 각 정점들이 연속된 수가 아닐 수 있기 때문이다. 즉, 문제에서 주어지는 정점들이 1, 2, 3, 4처럼 연속된 수가 아니라 1, 3, 6, 8와 같을 수도 있다는 것이다. 따라서 i = 1부터 max 값까지 차례대로 수행되는데 i가 문제에서 주어지지 않는 숫자일 때, 위 코드대로라면 out.get(i).size()의 값이 0이기 때문에 막대 그래프라고 판단하게 된다.

 

따라서 막대 그래프를 판단할 때는 나가는 선이 없으면서 들어오는 선의 갯수가 1개 이상이어야 한다.

• 들어오는 선의 갯수가 1개라고 생각하면 안된다(in.get(i).size() == 1). 추가된 정점이 해당 정점으로 선을 그을 수 있기 때문에 이 경우에는 들어오는 선의 갯수가 2개이기 때문이다.
• 따라서 들어오는 선의 갯수가 1개 이상이어야 한다. 

import java.util.*; 

class Solution {
    public int[] solution(int[][] edges) {
        Map<Integer, List<Integer>> out = new HashMap<>();
        Map<Integer, List<Integer>> in = new HashMap<>();
        int max = 0;
        for (int[] edge : edges) {
            max = Math.max(max, Math.max(edge[0], edge[1]));
        }
        
        for (int i = 1; i <= max; i++) {
            out.put(i, new ArrayList<>());
            in.put(i, new ArrayList<>());
        }
        
        for (int[] edge : edges) {
            List<Integer> list1 = out.get(edge[0]);
            list1.add(edge[1]);
            out.put(edge[0], list1);
            
            List<Integer> list2 = in.get(edge[1]);
            list2.add(edge[0]);
            in.put(edge[1], list2);
        }
        
        // 정점: 나가는 선 2개 이상 + 들어오는 선 없음
        int node = 0;
        for (int i = 1; i <= max; i++) {
            if (out.get(i).size() >= 2 && in.get(i).size() == 0) {
                node = i;
                break;
            }
        }
        int totalCnt = out.get(node).size();
        
        // 8자: 나가는 선 2개
        int eight = 0;
        for (int i = 1; i <= max; i++) {
            if (i == node) continue;
            if (out.get(i).size() == 2) {
                eight++;
            }
        }
        
        // 막대: 나가는 선 없음 + 들어오는 선 1개 이상
        int bar = 0;
        for (int i = 1; i <= max; i++) {
            if (i == node) continue;
            if (out.get(i).size() == 0 && in.get(i).size() >= 1) {
                bar++;
            }
        }
        
        // 생성한 정점 번호, 도넛 수, 막대 수, 8자 수 반환
        return new int[]{node, totalCnt - (bar + eight), bar, eight};
    }
}