programmers - 그래프 - 순위

문제 설명

n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다.

선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

∙ 선수의 수는 1명 이상 100명 이하입니다.
∙ 경기 결과는 1개 이상 4,500개 이하입니다.
∙ results 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미입니다.
모든 경기 결과에는 모순이 없습니다.
∙ 하위그룹으로 2번 5번의 순서는 확실하고 상위그룹으로 4번과 3번의 순서도 정해져있지만 1번의 경기 전적이 하나 밖에 없어서 최종적으로 1, 3, 4번의 순위를 결정할 수 없는 상황이라고 판단했다.

입출력 예 설명

2번 선수는 [1, 3, 4] 선수에게 패배했고 5번 선수에게 승리했기 때문에 4위입니다.
5번 선수는 4위인 2번 선수에게 패배했기 때문에 5위입니다.

function solution(n, results) {
    let idx = 0;
    let boxers = new Array(n).fill(0);
    boxers = boxers.map(a => [[],[]]);

    for(let i = 0; i < results.length; i++){
        let result = results[i];
        boxers[result[0]-1][1].push(result[1]);
        boxers[result[1]-1][0].push(result[0]);    
    }
    
    
    while(idx < n){
        for(let i = 0; i < results.length; i++){
            let result = results[i];
            let r1 = result[0];
            let r2 = result[1];
            
            for(let j = 0; j < boxers.length; j++){
                let boxer = boxers[j];
                let b1 = boxer[0];
                let b2 = boxer[1];
                if(b1.length + b2.length === n-1) continue
                if(b1.includes(r2)){
                    if(!b1.includes(r1)) b1.push(r1)
                }
                if(b2.includes(r1)){
                    if(!b2.includes(r2)) b2.push(r2)
                }
            }
        }
        
        idx++;
    }
    
    return boxers.filter(a => {return a[0].length + a[1].length === n-1 ? true : false}).length;
}

하지만 다른 분의 주어진 해답 코드를 보면서 처음 생각한 방향으로는 문제 접근 및 해결에 도움이 되지 않는다. 주어진 모든 결과 데이터를 바탕으로 확실하게 추론할 수 있는 각 선수의 승리, 패배를 갱신 해주어야 한다. 각 단계로 정리해보면 다음과 같다.

1) 주어진 경기 결과를 1차적으로 정리해주는 boxers 배열을 선언.

2) 통해서 선수의 총 인원만큼 [ [ ], [ ] ] 형태로 자신을 상대로 이긴 선수와 패배한 선수를 순서대로 각각 넣는다.

3) 경기 결과 데이터를 하나하나 반복문으로 확인한다. 첫 번째 결과인 [4,3] 이라면 r1 = 4, r2 =3 로 놓고 경기 결과가 망라된 boxers의 값들과 비교해서 if문으로 확실하게 승리, 패배를 가늠할 수 있는 데이터면 b1, b2에 넣어준다.

4) 나머지 4명과의 승리, 패배를 확실하게 추론할 수 있는 boxers의 요소들을 뽑고 그것의 길이를 return하면 된다.

참고한 솔루션 코드: https://www.hamadevelop.me/dailyblogging11%20/