2024 카카오 채용 연계형 겨울 인턴십 코딩테스트 2번 - 문제풀이

도넛과 막대 그래프

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

루트노드번호,도넛그래프갯수,막대그래프갯수,8자그래프갯수를 반환해줘야하는 문제였다.
막대그래프부분 이해하는데만 한참걸렸다 실제 코테에서는 이문제를 풀다가 시간을 다써서 끝이났다.
지문이 길어지니 참 이해하기 어려웠는데 루트노드를 찾는 조건은 들어오는 간선은 없고 나가는 간선만 2개이상이면서 최대 간선을 보유하고 있는 노드가 루트노드의 조건이고
막대 그래프는 나가는 간선은 없고 들어오는 간선은 없거나 1개일때or 1개 이상이 될수도있다.
8자 그래프는 나가는 간선 2개 들어오는 간선 2개 의 조건을 맞춰주면 8자 그래프라고 얘기할수있는 것이다. 도넛그래프는.. 이것을 한참이해하려고 했으나 아직도 잘 이해가 가지않는다 다른 문제풀이들을 보니 전체 그래프갯수에서 - (막대그래프갯수 + 8자그래프갯수)로 구하더라 좀 어이가없었다 ㅎㅎ..

코드를 보자

function solution(edges) {
  let answer = new Array(4).fill(0)
  let graph = {}
  for (const [a,b] of edges) {
    if(!graph[a]){
      graph[a] = [0,0] // 각 노드에서 in-degree, out-degree 를 저장해줄 용도이다
    }
    if(!graph[b]){
      graph[b] = [0,0] // 각 노드에서 in-degree, out-degree 를 저장해줄 용도이다
    }
    graph[a][0]++ // in-degree를 카운트해준다
    graph[b][1]++ // out-degree를 카운트해준다
  }
  for (const key in graph) {
    if(graph[key][0] >= 2 && graph[key][1] === 0){
      answer[0] = Math.max(answer[0],key)
      // in-degree가 2개이상이면서 out-degree가 0개이다 그중에 in-degree가 가장많은 노드를 선택한다
    }
  }
  let total = graph[answer[0]][0] // 나중에 도넛그래프의 갯수를 구하기위해 변수로 저장해뒀다
  for (const [a,b] of edges) {
    if(a !== answer[0])continue
    graph[b][1]-- 
    // 여기서 중요하다 막대그래프 조건이 가장애매했는데 루트노드에서
  	// in-degree를 graph에서 다 제거해준다 그러니 막대그래프를 찾을수 있었다.
  }
  for (const key in graph) {
    if(graph[key][0] === 0 && graph[key][1] >= 0){ // 막대그래프이다 
      answer[2]++
    }else if(graph[key][0] === 2 && graph[key][1] === 2){ // 8자그래프이다 
      answer[3]++ 
    }
  }
  answer[1] = total - (answer[2]+answer[3]) 
  // 그래프의 총갯수 - (막대그래프 + 8자그래프) 이렇게 하면 나머지가 도넛그래프가 되는것이다.
  return answer 
}

알고리즘 공부하면서 느끼는점은 나만빼고 다 똑똑한것같다 ㅎㅎ