[JS/LV2]도넛과 막대 그래프

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

프로그래머스

 

문제 요건

크기가 n인 도넛 모양 그래프는 n개의 정점과 n개의 간선이 있습니다.
크기가 n인 막대 모양 그래프는 n개의 정점과 n-1개의 간선이 있습니다.
크기가 n인 8자 모양 그래프는 2n+1개의 정점과 2n+2개의 간선이 있습니다. 
이 그래프들과 무관한 정점을 하나 생성한 뒤, 각 도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프의 임의의 정점 하나로 향하는 간선들을 연결했습니다.
그래프의 간선 정보를 담은 2차원 정수 배열 edges가 매개변수로 주어집니다. 이때, 생성한 정점의 번호, 도넛 모양 그래프의 수, 막대 모양 그래프의 수, 8자 모양 그래프의 수를 순서대로 1차원 정수 배열에 담아 return 하도록 solution 함수를 완성해 주세요.
리턴값 : [생성한 정점의 번호, 도넛모양 그래프의 수, 막대 모양 그래프의 수, 8자 모양 그래프의 수]

 

언뜻보면 dfs나 bfs 인가 싶지만 단순한 수학 문제에 가깝다. 대신 머리를 굴려야하는...

edges의 길이가 백만이 넘기때문에 잘못풀었다간, 런타임 오류와 시간 초과를 만날 수 있다.

다 풀고 나니, 문제에 힌트가 존재함을 느꼈다.

이 그래프들과 무관한 정점을 하나 생성한 뒤, 그래프의 임의의 정점 하나로 향하는 간선들을 연결했습니다.

 

이 부분이다. 이걸 주의깊게 생각하면 쉽게 풀 수 있다.(물론 난 오래걸렸고 자책과 함께 문제와 시간을 보냈다)

 

문제 풀이

문제는 연결된 정점이 어떻게생겼으며 뭐가 연결되어있는지 굳이 찾을 필요가 앖다.

연결된 간선의 갯수로 찾는 생각의 전환이 필요하다. 

 새로 생성된 정점을 찾을 겸, 정점에 연결된 간선의 갯수도 알아볼겸 for문으로 간선들을 객체&배열로 정리한다. 

여기서 나가고 들어오는 간선의 갯수를  배열 2개로 해서 풀게 된다면 런타임 오류를 만날 수 있다.

    let obj={}
    for(let [to,from] of edges){
        if(!obj[to]){
            obj[to]=[0,0]
        }
        if(!obj[from]){
            obj[from]=[0,0]
        }
        obj[to][0]+=1
        obj[from][1]+=1
    }

 

이제 간선들의 갯수로 각 그래프의 갯수를 구할 수 있다.

문제 속 그림을 보게 되면, 각 그래프의 특징이 보인다.

객체를 순회하면서  도넛 모양 그래프를 제외한 값들을 구할 수 있다.

 

우선 막대 그래프인 경우는 순환하지 않기 때문에, 하나는 무조건 to(나가는 간선)가 없이 끝나게 된다. 

막대 그래프의 갯수는 정점 중 to가 없는 정점의 갯수를 찾으면 된다.  

 

8자 모양 그래프는 그림을 봤을 때 가운데의 정점이 나가는 간선이 2개 들어오는 간선이 2개인걸 볼 수 있다.

새로 생긴 정점에 연결된걸 고려해서 to가 2 이상이면서, from이 2인 정점의 갯수를 세면 된다.

 

새로 생긴 정점은 from, 즉 들어온 간선이 없으면 새로 생긴 정점이다. 다만 막대 그래프의 첫번째 정점 또한 들어오는 간선이 없다.

이 때 정점을 구하려면 새로 생긴 정점의 특징을 생각하면 된다.

이때 총 그래프의 갯수인 total도 함께 구한다. 새로 생긴 정점의 to의 갯수가 총 그래프의 갯수가 되기 때문에 to의 크기가 기존의 값(total)보다 크다면 값을 계속 바꿔주면 된다.

 

  for(let key in obj){
        let [to,from]=obj[key]
        if(to>=2&&from>=2){
            ans[3]+=1
            //8자 그래프 갯수
        }
        if(to===0){
            ans[2]+=1
            //막대 그래프 갯수
        }
        if(from===0&&to>=ans[3]+ans[2]){
        //나같은경우 분기를 이렇게 했는데, 그냥 from===0만 해도 문제 풀린다 
            if(total<to){
                ans[0]=Number(key)
                total=Number(to)
            }
        }
    }

 

마지막으로 도넛 모양 그래프는 앞에서 구한 총 그래프의 갯수 total에서 8자 모양 그래프의 수, 막대 모양 그래프의 수를 빼면 된다.

  ans[1]=total-ans[3]-ans[2]

최종 코드

function solution(edges) {
    let ans=new Array(4).fill(0)
    let obj={}
    let total=0
    for(let [to,from] of edges){
        if(!obj[to]){
            obj[to]=[0,0]
        }
        if(!obj[from]){
            obj[from]=[0,0]
        }
        obj[to][0]+=1
        obj[from][1]+=1
    }
    for(let key in obj){
        let [to,from]=obj[key]
        if(to>=2&&from>=2){
            ans[3]+=1
        }
        if(to===0){
            ans[2]+=1
        }
        if(from===0&&to>=ans[3]+ans[2]){
            if(ans[0]===0){
                ans[0]=Number(key)
                total=to
                continue
            }
            if(obj[ans[0]][0]<to){
                ans[0]=Number(key)
                total=Number(to)
            }
        }
    }
    ans[1]=total-ans[3]-ans[2]
  return ans  
}