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

📍 문제 풀이

* 카카오 테크의 문제 풀이 발췌

 

이 문제는 세 가지 모양의 그래프와 생성된 정점의 특징을 분석하는 것이 핵심인 문제입니다. 각 그래프의 모양은 아래와 같습니다.

 

• 생성된 정점 : 나가는 간선이 2개 이상(그래프의 개수 만큼) 존재, 들어오는 간선이 없음
• 막대 : 생성된 정점과 연결된 간선을 제외했을 때, 들어오는 간선이 없는 정점 1개, 나가는 간선이 없는 정점 1개 (두 정점이 같을 수 있음), 나머지 정점은 나가는 간선과 들어오는 간선이 하나씩 존재
• 도넛 : 생성된 정점과 연결된 간선을 제외했을 때, 모든 정점이 나가는 간선과 들어오는 간선이 1개씩 존재
• 8자 : 생성된 정점과 연결된 간선을 제외했을 때, 1개를 제외하면 나가는 간선과 들어오는 간선이 1개씩 존재, 1개의 정점은 나가는 간선과 들어오는 간선이 2개씩 존재

---

 

🙋🏻‍♀️ 내 풀이 방식 : new node가 가리키는 각각의 그래프를 bfs 탐색하여 node, edge수를 구하고 어떤 그래프인지 판단

💻 공식 풀이 : in-degree(진입 차수)/out-degree(진출 차수)를 탐색하여 그래프의 구조를 판별

 

나는 처음부터 진입 차수, 진출 차수를 사용해서 풀이하는 방법이 떠오르지 않아서, 그래프 형태를 파악하기 위해 완전 탐색하며 node, edge 수를 구했다. 문제에서도 정점, 간선 특징을 명확하게 주었고 애초에 도넛, 막대, 8자 세 가지 형태만 존재하며 각 그래프가 독립적으로 존재한다는 게 확실해서 내 풀이 방법이 틀렸다는 게 잘 이해가 가지 않았다..

 

그래서 어제부터 계속 테케를 시뮬레이션 해보고 지피티에게 물어보면서 디버깅 해봤는데 문제를 몇 번이나 먹이고 지적해도 계속 이상한 반례만 주길래 잠깐 쉬고 오늘 다시 해봤는데 통과되었다. 👏🏻  완전탐색으로 인해 속도와 메모리는 떨어지지만 생각해낸 아이디어로 구현을 성공했다는 점에서 의미있었다. (더 효율적인 코드는 아래를 참고)

 

내가 놓친 로직 : newNode를 구할 때 진출 차수가 2개 이상이어야 함

시간 초과 해결한 부분 : 방문 체크를 int에서 boolean으로 변경

 

📍 정답 코드

내 코드는 다음과 같고, 카카오 테크에서 권장한 방법으로도 풀어봤다.

import java.util.*;
class Solution {
    public int[] solution(int[][] edges) {
        /*
        새 정점 : 나가는 간선만 존재하고, 2개 이상인 경우
        도넛 그래프 : 원래 출발했던 정점으로 돌아오는 경우
        막대 그래프 : 지나온 정점 수보다 1 적게 이동한 경우
        8자 그래프 : 2n+1개의 정점, 2n+2개의 간선인 경우
        
        - hashmap에서 key에 해당하는 value를 모두 큐에 넣고 node, edge 수 카운트
        - 단, 방문한 정점을 또 방문했다면 
            - value를 큐에 넣지 않기
            - node 수 카운트하지 않기
        */
        int donut = 0;
        int stick = 0;
        int eight = 0;

        int maxNode = 0;
        for(int[] e : edges){
            maxNode = Math.max(maxNode, Math.max(e[0], e[1]));
        }

        int[] indegree = new int[maxNode+1];
        int[] outdegree = new int[maxNode+1];

        Map<Integer, List<Integer>> map = new HashMap<>();
        int newNode = 0;

        for(int i=1; i<=maxNode; i++){
            List<Integer> list = new ArrayList<>();
            map.put(i, list);
        }

        for(int[] e : edges){
            outdegree[e[0]]++;
            indegree[e[1]]++;
            map.get(e[0]).add(e[1]);
        }

        for(int i=0; i<indegree.length; i++){
            if(indegree[i]==0 && outdegree[i]>=2){
                newNode = i;
                break;
            }
        }

        for(int i=0; i<map.get(newNode).size(); i++){
            int nodeCnt = 0;
            int edgeCnt = -1; //newNode와 이어지는 간선은 제외하고 카운트

            Queue<Integer> q = new LinkedList<>();
            q.offer(map.get(newNode).get(i));
            boolean[] visited = new boolean[maxNode+1];

            while(!q.isEmpty()){
                int n = q.poll(); //큐에서 하나 꺼내서

                if(visited[n]){ //이미 방문했다면
                    edgeCnt++;
                    continue; //간선만 하나 세기
                }

                //아직 방문하지 않았다면 
                for(int j=0; j<map.get(n).size(); j++){ 
                    q.offer(map.get(n).get(j));//꺼낸 노드에서 나가는 화살표 모두 큐에 넣기
                }
                visited[n] = true; //방문체크
                edgeCnt++; //노드와 간선 세기
                nodeCnt++;
            }

            /*
            도넛 그래프 : n개의 정점, n개의 간선이고 원래 출발했던 정점으로 돌아오는 경우
            막대 그래프 : 지나온 정점 수보다 1 적게 이동한 경우
            8자 그래프 : 2n+1개의 정점, 2n+2개의 간선인 경우
            */

            if(nodeCnt-1 == edgeCnt){
                stick++;
            } else if(nodeCnt == edgeCnt){
                donut++;
            } else if(nodeCnt+1 == edgeCnt){
                eight++;
            }
        }
            int[] ans = {newNode, donut, stick, eight};
            return ans;
    }
}

 

 

다른 사람 풀이를 참고해서 정말 간단하게 풀었다.

각 그래프의 특징을 잘 파악해서 조건문을 다시 세웠다.

import java.util.*;
class Solution {
    public int[] solution(int[][] edges) {
        
        int maxNode = 0;
        for(int[] e : edges){
            maxNode = Math.max(Math.max(e[0], e[1]), maxNode);
        }
        
        int[] in = new int[maxNode+1];
        int[] out = new int[maxNode+1];
        
        //각 노드의 진입, 진출 차수 구하기
        for(int[] e : edges){
            out[e[0]]++;
            in[e[1]]++;
        }
        
        int newNode = 0;
        int donut = 0;
        int stick = 0;
        int eight = 0;
        
        /*
        새로운 노드 : 진출 2이상, 진입0
        막대 : 진출1 진입0 1개, 진출0 진입1 1개, 나머지는 모두 진출1 진입1
        도넛 : 모든 노드가 진출1 진입1
        8자 : 1개의 노드만 진출2 진입2, 나머지는 모두 진출1 진입1
        */
        
        for(int i=1; i<=maxNode; i++){
            if(out[i] >= 2){
                if(in[i] == 0){
                    newNode = i;
                    continue;
                }else{
                    eight++;
                }
            }else if(out[i] == 0 && in[i] >= 1){
                    stick++; 
            }
        }
        
        donut = out[newNode] - stick - eight;
        
        int[] ans = {newNode, donut, stick, eight};
        return ans;
    }
}

 

📍성능 비교

2가 훨씬 빠르고 메모리도 적게 필요하다.

실행 시간은 40~100배, 메모리 사용량은 약 3~5배 차이났다.

 

코드1

테스트 1 〉	통과 (0.34ms, 76.9MB)
테스트 2 〉	통과 (0.99ms, 84.1MB)
테스트 3 〉	통과 (1.46ms, 71.9MB)
테스트 4 〉	통과 (0.55ms, 93.1MB)
테스트 5 〉	통과 (1.88ms, 93.3MB)
테스트 6 〉	통과 (1.46ms, 90.1MB)
테스트 7 〉	통과 (1.43ms, 74.1MB)
테스트 8 〉	통과 (447.22ms, 565MB)
테스트 9 〉	통과 (3259.47ms, 481MB)
테스트 10 〉	통과 (1739.16ms, 535MB)
테스트 11 〉	통과 (518.47ms, 531MB)
테스트 12 〉	통과 (504.30ms, 546MB)
테스트 13 〉	통과 (1249.80ms, 508MB)
테스트 14 〉	통과 (2914.39ms, 976MB)
테스트 15 〉	통과 (204.17ms, 234MB)
테스트 16 〉	통과 (278.40ms, 305MB)
테스트 17 〉	통과 (389.94ms, 309MB)
테스트 18 〉	통과 (311.51ms, 233MB)
테스트 19 〉	통과 (240.97ms, 218MB)
테스트 20 〉	통과 (262.48ms, 206MB)
테스트 21 〉	통과 (527.16ms, 395MB)
테스트 22 〉	통과 (476.62ms, 325MB)
테스트 23 〉	통과 (424.82ms, 360MB)
테스트 24 〉	통과 (422.53ms, 326MB)
테스트 25 〉	통과 (403.92ms, 336MB)
테스트 26 〉	통과 (408.00ms, 350MB)
테스트 27 〉	통과 (0.20ms, 70.9MB)
테스트 28 〉	통과 (0.17ms, 80.2MB)
테스트 29 〉	통과 (0.20ms, 87.2MB)
테스트 30 〉	통과 (0.14ms, 80.5MB)
테스트 31 〉	통과 (0.22ms, 85.6MB)
테스트 32 〉	통과 (0.19ms, 78.1MB)
테스트 33 〉	통과 (0.18ms, 69.8MB)
테스트 34 〉	통과 (0.14ms, 79MB)
테스트 35 〉	통과 (0.20ms, 87.4MB)

코드2

테스트 1 〉	통과 (0.04ms, 76.6MB)
테스트 2 〉	통과 (0.13ms, 81MB)
테스트 3 〉	통과 (0.09ms, 76.1MB)
테스트 4 〉	통과 (0.06ms, 72.6MB)
테스트 5 〉	통과 (0.18ms, 85MB)
테스트 6 〉	통과 (0.12ms, 80.1MB)
테스트 7 〉	통과 (0.11ms, 84MB)
테스트 8 〉	통과 (18.79ms, 147MB)
테스트 9 〉	통과 (30.47ms, 126MB)
테스트 10 〉	통과 (25.93ms, 145MB)
테스트 11 〉	통과 (20.58ms, 138MB)
테스트 12 〉	통과 (22.99ms, 157MB)
테스트 13 〉	통과 (22.15ms, 158MB)
테스트 14 〉	통과 (31.18ms, 196MB)
테스트 15 〉	통과 (24.29ms, 161MB)
테스트 16 〉	통과 (11.02ms, 128MB)
테스트 17 〉	통과 (21.82ms, 169MB)
테스트 18 〉	통과 (18.72ms, 156MB)
테스트 19 〉	통과 (25.62ms, 130MB)
테스트 20 〉	통과 (22.34ms, 153MB)
테스트 21 〉	통과 (24.91ms, 192MB)
테스트 22 〉	통과 (28.33ms, 157MB)
테스트 23 〉	통과 (23.67ms, 152MB)
테스트 24 〉	통과 (28.38ms, 158MB)
테스트 25 〉	통과 (22.95ms, 178MB)
테스트 26 〉	통과 (23.62ms, 168MB)
테스트 27 〉	통과 (0.02ms, 86.1MB)
테스트 28 〉	통과 (0.03ms, 82.3MB)
테스트 29 〉	통과 (0.03ms, 76.6MB)
테스트 30 〉	통과 (0.03ms, 73.1MB)
테스트 31 〉	통과 (0.02ms, 81.8MB)
테스트 32 〉	통과 (0.04ms, 74.2MB)
테스트 33 〉	통과 (0.02ms, 76.1MB)
테스트 34 〉	통과 (0.03ms, 74.5MB)
테스트 35 〉	통과 (0.03ms, 90.3MB)