[프로그래머스 C#] Lv.2 도넛과 막대 그래프

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

프로그래머스

1. 정답코드 및 핵심 아이디어, 유의사항

그래프 순회로 풀면 시간초과

- 처음엔 그래프 순회를 하려고 생성한 정점의 번호를 구하고, 이어진 정점을 딕셔너리에 담아서 탐색하려고 했는데, 생성한 정점을 구하다보니 결국 그래프도 개수만 알면 되기에 생성한 정점의 번호를 구하듯이 구할 수 있을 것 같다는 아이디어에서 시작

( 생각보다 제한 시간이 넉넉해서 바로 통과가 되버리는 바람에 매우 비효율적인 코드가 나의 풀이에 박제되어 가슴이 아픔.... )

 

간선 [ a, b ] 일 때, a는 b정점에게 주고, b는 a에게 받는다.

- 생성한 정점 : 받은 횟수 x, 준 횟수 o

- 막대 그래프 특이 정점 : 받은 횟수 o, 준 횟수 x

- 8자 그래프 특이 정점 : 받은 횟수 2회 이상, 준 횟수 2회 ( 생성한 정점이 가리킬 수 있기 때문 )

- 도넛 그래프는 특이 정점 : 없음

 -> 전체 그래프의 개수(생성한 정점의 준 횟수)에서 막대 그래프와 8자 그래프를 뺀 값으로 구함

 

위 내용을 표로 정리

	받은 횟수	준 횟수	비고
생성한 정점	X	O	생성한 정점은 받지 않고 주기만 함 (그래프는 2개 이상)
막대 그래프 특이 정점	O	X	막대 그래프의 가장 끝 인덱스는 누구에게도 유일하게 주지 않는 정점
8자 그래프 특이 정점	2 이상	2	8자 그래프의 중앙은 유일하게 2개 이상 주고 2개 이상 받는 정점
도넛 그래프 특이 정점	특이 정점이 없어 전체 그래프의 개수(생성한 정점의 준 횟수)에서 다른 그래프의 개수를 뺀 값

 

 

주석 참조

    using System;
    using System.Collections.Generic;

    public class Solution
    {
        public class DataClass
        {
            public int giveCount;
            public int receiveCount;

            public DataClass()
            {
                giveCount = 0;
                receiveCount = 0;
            }
        }

        public int[] solution(int[,] edges)
        {
            int[] answer = new int[4] { 0, 0, 0, 0 };

            var dict = new Dictionary<int, DataClass>(); // 주고 받은 정점의 수
            int maxNum = 0; // 정점의 개수

            // dict에 값 세팅 (정점에 대한 간선에 정보를 세팅)
            for (int i = 0; i < edges.GetLength(0); i++)
            {
                int giveNum = edges[i, 0];
                int receiveNum = edges[i, 1];
                
                // 정점의 개수 구하기
                if (maxNum < giveNum) maxNum = giveNum;
                if (maxNum < receiveNum) maxNum = receiveNum;
                
                if (dict.ContainsKey(giveNum) == false)
                    dict.Add(giveNum, new DataClass());
                if (dict.ContainsKey(receiveNum) == false)
                    dict.Add(receiveNum, new DataClass());
                    
                // 주고 받은 정점의 개수 카운트
                dict[giveNum].giveCount++;
                dict[receiveNum].receiveCount++;
            }

            // 생성한 정점과 특이 정점 찾기
            for (int i = 1; i <= maxNum; i++)
            {
                int receiveCount = dict[i].receiveCount;
                int giveCount = dict[i].giveCount;

                if (receiveCount == 0 && giveCount >= 2)
                {
                    // 생성한 정점
                    answer[0] = i;
                }
                else if (dict[i].giveCount == 0)
                {
                    // 막대 모양 그래프
                    answer[2]++;
                }
                else if (dict[i].receiveCount >= 2 &&
                       dict[i].giveCount >= 2)
                {
                    // 8자 모양 그래프
                    answer[3]++;
                }
            }

            // 도넛 모양 그래프는 특이정점이 없으므로 전체 개수에서 나머지 그래프 개수 뺀 나머지를 넣어줌
            answer[1] = dict[answer[0]].giveCount - answer[2] - answer[3];

            return answer;
        }
    }