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

문제 설명

도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프가 여러 개 있습니다. 이 그래프들과 무관한 정점을 하나 생성한 뒤, 각 도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프의 임의의 정점 하나로 향하는 간선들을 연결했습니다. 그 후 각 정점에 서로 다른 번호를 매겼습니다. 이때 당신은 그래프의 간선 정보가 주어지면 생성한 정점의 번호와 정점을 생성하기 전 도넛 모양 그래프의 수, 막대 모양 그래프의 수, 8자 모양 그래프의 수를 구해야 합니다.

그래프의 간선 정보를 담은 2차원 정수 배열 edges가 매개변수로 주어집니다. 이때, 생성한 정점의 번호, 도넛 모양 그래프의 수, 막대 모양 그래프의 수, 8자 모양 그래프의 수를 순서대로 1차원 정수 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

 

문제 풀이

해당 모양마다, 간선의 in 갯수와, out의 갯수가 다른 것을 확인 할 수있었다.
1. 도넛 모양인 경우 input과 output이 1개씩 있는 것으로 확인
2. 막대 모양인 경우 input과 output이 1개씩 있는 것으로 확인 => 마지막 node 경우 input이 있지만 output이 없는 것을 알 수 있다.
3. 8자 모양인 경우 input과 output이 2, 2개 씩 있는 node를 확인,

따라서 2번과 3번을 구하면, 총 정점에서 나간 간선의 갯수에서 해당 번호의 차를 통해 1번을 구할 수 있다. 

 

코드

import java.util.HashMap;

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

        for (int[] edge : edges) {
            out.put(edge[0], out.getOrDefault(edge[0], 0) + 1);
            in.put(edge[1], in.getOrDefault(edge[1], 0) + 1);
        }

        for (int key : out.keySet()){
            if (out.get(key) > 1){
                if (!in.containsKey(key)) answer[0] = key;
                else answer[3]++;
            }
        }

        for (int key : in.keySet()) if (!out.containsKey(key)) answer[2]++;


        answer[1] = out.get(answer[0]) - answer[2] - answer[3];
        return answer;
    }
}

 

깨달은 점

처음에 코드를 만들고 output의 key로 input이 없는 것으로 막대 모양을 찾을려다가, 틀렸다 라는 답변을 받고 다시 생각해보는 경험을 했다. 틀렸을 때, 나의 코드의 이유를 찾아가며 문제를 해결한다면 좋은 결과로 이어진다는 생각을 다시 받는다. 
또 하나 HashMap에서 지원하는 method 까먹자 말자 put을 push로 기억하던가 등등