도넛과 막대 그래프

프로그래머스 기출 문제중 하나로 도넛과 막대 그래프 문제이다. 문제의 설명은 이렇다.

도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프가 여러 개 있습니다. 이 그래프들과 무관한 정점을 하나 생성한 뒤, 각 도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프의 임의의 정점 하나로 향하는 간선들을 연결했습니다. 그 후 각 정점에 서로 다른 번호를 매겼습니다. 이때 당신은 그래프의 간선 정보가 주어지면 생성한 정점의 번호와 정점을 생성하기 전 도넛 모양 그래프의 수, 막대 모양 그래프의 수, 8자 모양 그래프의 수를 구해야 합니다.그래프의 간선 정보를 담은 2차원 정수 배열 edges가 매개변수로 주어집니다. 이때, 생성한 정점의 번호, 도넛 모양 그래프의 수, 막대 모양 그래프의 수, 8자 모양 그래프의 수를 순서대로 1차원 정수 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

즉 문제는 여러 점과 점을 이은 배열의 배열을 파라미터에 보냈을때 모양들의 연결 노드, 도넛, 막대기, 팔자모양의 개수를 리턴하는 문제였다.

처음에는 연결되는 모든 노드들을 따로 다른 배열에 넣어서 모양을 확인하는 방식으로 풀어보려고 했지만 너무 많은 for() 루프와 if() 를 사용해야 했기 때문에 코드가 너무 지저분 하였다. 하지만 생각해보면 도형의 개수는 모든 노드들을 확인 할 필요 없이 연결된 선의 개수만으로도 알수있었다.

막대 모양은 항상 끝에 연결선이 하나인 노드의 개수로 확인하면 되었고, 팔자모양는 가운데 노드가 나가고 들어오는 선이 2개씩 있으면 되었다. 각 모양을 찾는 방법을 정리해보면:

• 막대모양: 연결선이 하나인 노드
• 팔자모양: 들어오고 나가는 선이 두개인 노드
• 모든 모양과 연결된 노드: 들어오는 선은 없으며 나가는 선만 있는 노드 (이때 모양의 총 개수를 알 수 있다)
• 도넛모양: 총 모양 개수 - 막대모양 개수 - 팔자모양 개수

풀이:

1function solution(edges) {
2    const map = {}
3
4		// for loop를 사용해 각 노드의 객체를 만들어 들어 오는 선과 나가는 선의 개수를 저장한다
5		// 예시 { 1 : [1,2] } --> 1노드는 1개의 들어오는 선과 2개의 나가는 선이 있다. 
6    for (const [start, end] of edges) {
7        map[start] = map[start] ?? [0, 0]
8        map[end] = map[end] ?? [0, 0]
9        map[start][0]++
10        map[end][1]++
11    }
12
13    let addedNode = 0 // 모든 모양과 연결된 노드
14    let donutCnt = 0
15    let lineCnt = 0
16    let eightCnt = 0
17    for (const [start, [given, received]] of Object.entries(map)) {
18        if (given > 1 && received === 0) {
19            addedNode = start
20        } else if (given === 0) {
21            lineCnt++
22        } else if (given > 1 && received > 1) {
23            eightCnt++
24        }
25    }
26
27    donutCnt = map[addedNode][0] - lineCnt - eightCnt
28
29    return [Number(addedNode), donutCnt, lineCnt, eightCnt]
30}