[프로그래머스 2단계] 도넛과 막대 그래프

❓문제 설명

• 3종류의 그래프가 있다 도넛과 막대와 8자 각각의 형태는 사이즈별로 간선과 정점의 개수가 일정하게 증가하는 추세이다
• 어떠한 연결점을 만들었다 치고 이 연결점이 무엇인지와 각각의 그래프는 몇개인지를 배열로 return하라고 한다

✅ 문제 해결

• 문제를 어떻게 해결해야 할지 감이 안와서 이부분은 다른 사람의 풀이를 보고 분석을 하면서 어떻게 구상을 하게 되었는지를 파악해보자
• 간선의 개수와 특징을 통해서 문제를 파악하는 것이 중요하다고 생각된다.
• 찾을 수 있는 규칙으로는 생성된 연결점은 나가는 선만 있고 들어오는 선이 없다는 내용과
• 8자의 중심에 위치한 수는 나가는 수와 들어오는 수가 각각 2개씩이며 이 중심 개수를 통해서 8자의 개수를 파악할 수 있다
• 라인의 경우 받는 선이 1개만 있는 중심이 1개가 있기에 이를 통해서 개수를 파악할 수 있다.
• 도넛의 경우에는 개수를 파악하기가 힘들다고한다 그렇기에 구하는 방식은 생성된 연결점에서 생성되는 간선의 개수 - 8자 - 라인 이렇게하면 도넛이 나오는데 도넛을 찾기 힘든 이유는 주고 받는선이 1개씩 존재하고 중심을 찾기가 힘들기 때문이다 그렇기에 8자에 있는 녀석돠 라인에 있는 녀석인지 도넛에 있는 녀석인지 구분할 수 없음

 

🔥 인상 깊은 남의 풀이

const getInfo = (edges) => { 
    const info = edges.reduce((map, key) => {
    if (!map.has(key[0])) {
        map.set(key[0], [1, 0]);
    } else {
        const [give, receive] = map.get(key[0]);
        map.set(key[0], [give+1, receive]);
    }
    if(!map.has(key[1])){
        map.set(key[1], [0, 1]);
    } else {
        const [give, receive] = map.get(key[1]);
        map.set(key[1], [give, receive+1]);
    }
    return map;
}, new Map());
    return info;
}

const chkInfo = (info) => {
    const res = new Array(4).fill(0); 
    for(const [key, io] of info){ 
        const [give, receive] = io;  
        if( 2 <= give && receive == 0) { 
            res[0] = key;
        } else if(give == 0) {
            //막대그래프 최상단은 give == 0
            res[2]++;
        } else if(give >= 2 && receive >= 2){
            res[3]++;
        }  
    }       
    // 도넛은 사이클이 이루어진다는 것 밖에 없기 때문에 개수 계산으로 판별할 수 없다. 
    // 생성 정점은 기존에 존재하던 모든 그래프에 간선을 하나 씩 연결한다.
    // 따라서, 생성 정점의 간선 개수에서 막대, 8자 그래프 개수를 빼면 도넛 그래프 개수가 나온다.
    res[1] = info.get(res[0])[0] - res[2] - res[3];
    return res;
}

const solution = (edges) => {
    const mapInfo = getInfo(edges);
    const answer = chkInfo(mapInfo);
    return answer;
}

function solution(edges) {
    const map = {}

    for (const [start, end] of edges) {
        map[start] = map[start] ?? [0, 0]
        map[end] = map[end] ?? [0, 0]
        map[start][0]++
        map[end][1]++
    }


    let addedNode = 0
    let donutCnt = 0
    let lineCnt = 0
    let eightCnt = 0
    for (const [start, [given, received]] of Object.entries(map)) {
        if (given > 1 && received === 0) {
            addedNode = start
        } else if (given === 0) {
            lineCnt++
        } else if (given > 1 && received > 1) {
            eightCnt++
        }
    }

    donutCnt = map[addedNode][0] - lineCnt - eightCnt

    return [Number(addedNode), donutCnt, lineCnt, eightCnt]
}

• 2가지의 풀이에 대해서 알아보았는데 동일하게 Map을 사용해서 간선을 구하려 한다.
• 중복된 값을 가지지 않는 Map을 통해서 중복된 key가 선언이 되었을 때 처리를 자연스럽게 해주는 것 같다.

 

❕느낀점

• 어떻게 풀어야할지 전혀 감이 오지 않아서 아직 많이 문법적으로 부족하고 알고리즘에 대한 지식도 좀 얕았다는 생각이 든다.
• 프로그래머스뿐만아니라 백준에서도 문제를 좀 풀면서 1단계 레벨을 좀 더 풀어야할지도 고민이 된다
• Map을 통해서 문제를 구현하는 방식에 대해 구조분해할당과 반복문을 잘 쓰면 코드가 훨씬 더 간단해지고 이해하기 좀 더 쉽다는 생각이 들었다.