99클럽 코테 스터디 12일차 TIL (챌린저): [프로그래머스][Java] 도넛과 막대 그래프 - level2

 

문제 보기

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

프로그래머스

 

 

풀이

나는 문제가 너무 어려워서 거의 답을 보고 풀었다.

혼자서 푸려고 했지만 계속 오답이 나왔다...

일단 그래프들의 특징을 찾아야 한다.

 

8자 모양

 

 

8자 모양 그래프는 중간에 나가는 간선 두 개, 들어오는 간선 두 개가 있는 노드가 존재한다는 특징이 있다.

 

막대 모양

 

막대 모양 그래프는 들어오는 간선은 있지만 나가는 간선은 없는 노드가 있다는 특징이 있다.

물론, 나가는 간선은 있지만 들어오는 간선은 없는 노드도 있다!

그러나 생성한 정점으로부터 간선이 들어오는 경우가 있을 수 있으니 이는 제외한다.

 

도넛 모양

 

혼자 문제를 풀며 제일 골치아팠던 그래프다.

나는 어떻게든 이 그래프의 특징을 찾으려 했는데 그럴 필요 없었다.

전체 그래프 - 다른 그래프를 빼면 도넛 모양 그래프의 수가 나오기 때문이다!

 

전체 그래프의 수?

생성한 노드에서 나가는 간선들의 수와 동일하다.

 

그럼 이제 코드를 살펴보자.

 

들어오는 간선, 나가는 간선

HashMap<Integer, Integer> nodeIn = new HashMap<>();
HashMap<Integer, Integer> nodeOut = new HashMap<>();

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

특정 노드에서 들어가는 간선, 나가는 간선의 수를 HashMap에 저장하였다.

 

생성한 정점, 8자모양 그래프 찾기

int nodeCount = 0;
for(Integer key : nodeOut.keySet()){
  if(nodeOut.get(key) >= 2){
    if(!nodeIn.containsKey(key)){
      answer[0] = key;
      nodeCount = nodeOut.get(key);
    } else {
      answer[3]++;
    }
  }
}

나가는 간선은 2개 이상이나 들어오는 간선은 없는 경우가 생성한 정점이 된다.

들어오는 간선도 있을 경우엔 위에서 말했다시피 8자 모양 그래프가 되기 때문에 배열의 3번째 항목을 증가시킨다.

겸사겸사 전체 그래프의 수(=생성한 정점의 나가는 노드 수)도 저장한다.

 

막대 모양 그래프 찾기

for(Integer key : nodeIn.keySet()){
  if(!nodeOut.containsKey(key)){
    answer[2] ++;
  }
}

들어오는 간선은 있으나 나가는 간선은 없는 노드가 발견될 경우 2번째 항목을 증가시켰다.

 

아래는 풀이법을 차용한 블로그이다.

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

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

 

 

전체 코드

import java.util.HashMap;

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

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

    int nodeCount = 0;
    for(Integer key : nodeOut.keySet()){
      if(nodeOut.get(key) >= 2){
        if(!nodeIn.containsKey(key)){
          answer[0] = key;
          nodeCount = nodeOut.get(key);
        } else {
          answer[3]++;
        }
      }
    }

    for(Integer key : nodeIn.keySet()){
      if(!nodeOut.containsKey(key)){
        answer[2] ++;
      }
    }

    answer[1] = nodeCount - (answer[2] + answer[3]);

    return answer;
  }
}

 

 

GitHub 링크

https://github.com/MetroDefro/CodingTest_AutoSave/tree/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/2/258711.%E2%80%85%EB%8F%84%EB%84%9B%EA%B3%BC%E2%80%85%EB%A7%89%EB%8C%80%E2%80%85%EA%B7%B8%EB%9E%98%ED%94%84

CodingTest_AutoSave/프로그래머스/2/258711. 도넛과 막대 그래프 at main · MetroDefro/CodingTest_AutoSave