Donut

1. 문제

코딩테스트 연습 - 도넛과 막대 그래프 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

2. 설명

각각의 특성을 파악하는 것이 우선이다.

먼저 그래프의 그림을 보자.

 

 

그리고 예제에 해당하는 그래프를 보자.

예 1

예 2

 

각각의 특징들을 나열해보자.

1. 생성된 노드 : 들어오는 간선은 없고, 나가는 간선이 2개 이상이다.
2. 막대 모양 그래프 : 나가는 간선 1개 + (들어오는 간선 1개 & 나가는 간선 1개) * N + 들어오는 간선 1개
3. 도넛 모양 그래프 : (들어오는 간선 1개 & 나가는 간선 1개) * N
4. 8자 모양 그래프 : 들어오는 간선 1개 & 나가는 간선 2개 + (들어오는 간선 1개 & 나가는 간선 1개) * N

위의 특징들로 답을 도출해보자.

1. 먼저 생성된 노드를 찾고 생성된 노드랑 관련된 간선들을 제거한다.
   이때 생성된 노드와 연결된 간선의 수는 전체 그래프의 개수와 같으니 따로 저장해 놓는다.
2. 3개의 그래프 중에 나가는 간선이 없는 노드는 막대 모양 그래프 뿐이다.
   나가는 간선이 없는 노드들의 개수를 세어 막대 모양 그래프로 카운팅한다.
3. 들어오고 나가는 간선의 개수가 2개를 가지는건 8자 모양 그래프 뿐이다.
   해당하는 노드들의 개수를 세어 8자 모양 그래프로 카운팅한다.
4. 전체 그래프의 개수에서 위 두 개 그래프의 개수를 빼면 남은 도넛 모양 그래프의 개수가 된다.

 

3. 코드

위 설명 대로 진행해도 문제가 해결되지만, 성능 이슈가 발생한다.

첫 코드를 저 특징대로 짰었는데, 반복문이 두 개가 넘을 시 몇몇 예제들에서 런타임 에러가 발생하였다.

이에 성능을 좀 더 높이기 위해 조금 변형을 했다.

 

[속도 이슈 해결 방법]

1. outcomming, incomming의 길이를 edges의 길이로 설정했었는데, 이것을 문제의 최대 길이인 1000000으로 고정시켜줬다.
   생각보다 length를 구하는 함수가 비효율적인가보다.
   문제에서 최대 길이가 설정되어 있다면, 그 수를 사용하는게 좋을것 같다.
2. 여러 반복문이 가장 큰 이슈였는데, 반복문을 하나로 줄여 해결하였다.
   들어오는 간선이 2개 이상일때 들어오는 간선이 없으면 생성된 노드일테고, 이외에는 8자 모양 그래프일 수 밖에 없다. 들어오는 간선이 2개 이상인 그래프는 8자 모양 그래프 하나이기 때문이다.
   그리고 간선이 2개 이상이 아닐때 나가는 간선이 없으면 막대모양 그래프일 수 밖에 없다.
   이렇게되어 생성된 노드를 찾는 반복문과 생성된 노드와 연결된 간선들을 제거하는 반복문이 줄어들게 되어 성능 향상을 바랄 수 있었다.
3. 추가로 find 노드에서 MaxLength로 코드 실행시 1번 예제가 11초로 해결 됐었는데, 이 또한 비효율적이라 생각하여 nodeSize를 구해서 길이를 제한하여 4초대로 줄였다.

public class Donut {
    static int MaxLength = 1000000;

    public static void main(String[] args){
        //int[][] edges = {{2, 3}, {4, 3}, {1, 1}, {2, 1}};
        int[][] edges = {{4, 11}, {1, 12}, {8, 3}, {12, 7}, {4, 2}, {7, 11}, {4, 8}, {9, 6}, {10, 11}, {6, 10}, {3, 5}, {11, 1}, {5, 3}, {11, 9}, {3, 8}};

        int[] result = solution(edges);
        for (int i = 0; i < result.length; i++) {
            System.out.println(result[i]);
        }
    }

    public static int[] solution(int[][] edges) {
        // answer =  생성한 점점의 번호, 정점을 생성하기전 도넛 모양 그래프의 수, 막대 모양 그래프의 수, 8자 모양 그래프의 수
        int[] answer = new int[4];

        int[] outcomming = new int[MaxLength];
        int[] incomming = new int[MaxLength];


        int nodeSize = 0;
        for (int i = 0; i < edges.length; i++){
            outcomming[edges[i][0]]++;
            incomming[edges[i][1]]++;

            if(edges[i][0] > nodeSize) nodeSize = edges[i][0];
            if(edges[i][1] > nodeSize) nodeSize = edges[i][1];
        }

        findNode(nodeSize, outcomming, incomming, answer);

        return answer;
    }

    static void findNode(int nodeSize, int[] outcomming, int[] incomming , int[] answer){
        int totalGraph = 0;
        for (int i = 1; i <= nodeSize; i++){
            if(outcomming[i] >= 2){
                if(incomming[i] == 0){
                    answer[0] = i;
                    totalGraph = outcomming[i];
                }else answer[3]++;
            }else if(outcomming[i] == 0) answer[2]++;
        }

        answer[1] = totalGraph - answer[2] - answer[3];
    }
}