99클럽 코테 스터디 12일차 TIL [Map]

- 오늘의 학습 키워드 : Map

[문제 이름 : 도넛과 막대 그래프 (카카오 겨울 인턴십 문제, LV 2)]
문제 url : https://school.programmers.co.kr/learn/courses/30/lessons/258711

내가 작성한 코드는 아래와 같다.

import java.util.*;

class Solution {
    public int[] solution(int[][] edges) {
        Map<Integer, Integer> startMap = new HashMap<>();
        Map<Integer, Integer> endMap = new HashMap<>();
        int[] answer = new int[4];

        // 정보 저장
        for (int[] edge : edges) {
            startMap.put(edge[0], startMap.getOrDefault(edge[0], 0) + 1);
            endMap.put(edge[1], endMap.getOrDefault(edge[1], 0) + 1);
        }

        
        for (int node : startMap.keySet()) {
            if (startMap.get(node) > 1) {
                if (!endMap.containsKey(node)) {
                    // 생성한 정점을 의미
                    answer[0] = node;
                } else {
                    // 8자 그래프를 의미
                    answer[3] += 1;
                }
            }
        }

        for (int node : endMap.keySet()) {
            if (!startMap.containsKey(node)) {
                // 도착 정점 중, 출발 간선이 없으면 막대 그래프
                answer[2] += 1;
            }
        }

        // 도넛 그래프 개수 = 생성한 정점 out 개수 - 막대 그래프 개수 - 8자 그래프 개수
        answer[1] = startMap.get(answer[0]) - answer[2] - answer[3];
        return answer;
    }
}

풀이 과정 (풀이 시간 : 1시간)

처음에는 그래프처럼 각자의 출발, 도착 정점에 따라 ArrayList<Integer>[]로 저장하려고 했는데, 도저히 이 방법이 아닌 것 같아서 방법을 많이 헤맸다. 타 블로그를 참고하여 문제의 아이디어를 떠올릴 수 있었다.

문제의 규칙성을 찾고자 접근을 다르게 해보았고, 아래와 같은 결론을 도출할 수 있었다.

 

A. 생성한 정점은 나가는 간선만 존재하며, 나가는 간선이 2개 이상 존재한다.

B. 도넛의 모든 정점은 들어오는 간선, 나가는 간선이 1개씩 존재한다.

C. 막대의 마지막 정점은 나가는 간선이 없다.

D. 8자 모양의 정점 중 한 개는 나가는 간선이 2개 있다.

	출발 간선(x)	도착 간선(x)
생성한 정점	x = 0	x > 1
도넛의 모든 정점	x >= 1	x = 1
막대의 마지막 정점	x >= 1	x = 0
8자의 하나의 정점	x >= 2	x = 2

 

1. 출발 정점과 도착 정점 정보에 따라, 2개의 Map을 통해 각각 저장한다.

2. startMap 간선 개수가 2개 이상인 정점 중, outMap의 간선이 없으면 생성한 정점이고, 있으면 8자 그래프이다.
3. endMap 간선이 있는 정점 중, startMap 간선이 없으면 막대 그래프이다.

4. 도넛 그래프는 생성한 정점의 startMap 간선 개수 - 막대 그래프 개수 - 8자 그래프 개수이다.

내일은 하반기 취업 준비를 위한 자기소개서를 작성할 예정이다.

 

[참고 블로그]

https://given-dev.tistory.com/104

[Programmers-Java] 도넛과 막대 그래프