[programmers/js] 순위

다단계 칫솔 판매

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

문제 설명

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

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

풀이

가장 중요한 조건은 등수를 구할 수 있는 사람의 조건을 찾는 것입니다.
예시에서 2번과 5번의 등수를 알 수 있는데 각 번호들은 자신이 이긴 번호 + 진 번호의 수가 n-1과 같다는 점을 알 수 있습니다.

예시 2번과 5번
2번은 1, 3, 4번에 지고 5번에 이겨 등수를 알 수 있습니다.
5번은 2번에 지는데, 2번은 1, 3, 4번에 져서 1, 2, 3, 4번 모두에게 진다고는 점을 알 수 있습니다.

위 조건을 통해 코드를 작성하면

• 1. 각 번호마다 이긴 번호, 진 번호를 기억합니다.
• 2. 각 번호마다 예시의 2, 5번 같은 경우를 계산해 줍니다.
     i번에게 진 사람은 i번을 이긴 사람에게 패함
     i번에게 이긴 사람은 i번에게 진 사람에게 이김
• 3. 등수를 알 수 있는지 확인합니다.

function solution(n, results) {
    const wins = {} // i번이 이긴 사람 목록, i번에게 진 사람 목록
    const loses = {} // i번이 진 사람 목록, i번에게 이긴 사람 목록

    for (let i = 0; i < n + 1; i++) {
        wins[i] = new Set([]);
        loses[i] = new Set([]);
    }
    
    for (const [win, lose] of results) {
        wins[win].add(lose);
        loses[lose].add(win);
    }
    
    for (let i = 1; i <= n; i++) {
        // i번에게 진 사람은 i번을 이긴 사람에게 패함
        // 5번은 2번에 져서, 5번을 이긴 목록(loses[5]에 2번을 이긴 사람(loses[2])이 포함되어야 함
        for (const loser of wins[i]) {
            if (!loses[loser]) continue;
            for (const winner of loses[i]) { // 이긴 사람 목록
                loses[loser].add(winner) // 추가
            }
        }
        
        // i번에게 이긴 사람은 i번에게 진 사람에게 이김
        for (const winner of loses[i]) {
            if (!wins[winner]) continue;
            for (const loser of wins[i]) { // 진 사람 목록
                wins[winner].add(loser) // 추가
            }
        }
    }
  
    // 최종 wins[i] + loses[i]가 n-1과 같으면 등수 확정 
    return Array.from({length: n }, (_, i) => i + 1).reduce((a, c) => {
        if (wins[c].size + loses[c].size === n - 1) return a + 1;
        return a
    }, 0);
}