[JS] 프로그래머스 순위

문제 링크

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

1차시도

N까지의 랭크 후보를 제거해갔다
문제점: [1, 2], [2, 3], [1, 4]와 같이 후보가 제거되지 않는 상황 발생

합계: 20.0 / 100.0

function solution(n, results) {
    const battle = [...Array(n)].map(_ => Array(n).fill(0));
    const rankList = [...Array(n)].map(_ => [...Array(n)].map((__, i) => i + 1));
    const rank = Array(n).fill(0);

    results.forEach(([a, b]) => {
        // 랭크 후보에서 제거하는 방식
        rankList[a - 1].pop();
        rankList[b - 1].shift();
        // 해당 친구에게 승리 1, 패배 2를 담는 그래프
        battle[a - 1][b - 1] = 1;
        battle[b - 1][a - 1] = 2;
    })

    while (rankList.some(v => v.length === 1))
        rankList.forEach((cand, i) => {
            if (cand.length === 1) {
                rank[i] = cand.pop();
                // 해당 선수가 결전한 친구들 랭크후보 최신화
                battle[i].forEach((winlose, j) => {
                    if (winlose === 1)
                        while (rankList[j].shift() < rank[i]);
                    if (winlose === 2)
                        while (rankList[j].pop() > rank[i]);
                });
            }
        });
    return rank.reduce((ac, v) => ac + (v ? 1 : 0), 0);
}

2차 시도

플로이드 와샬
a가 b를 이기고 b가 c를 이겼으면 a가 c를 이긴다.
최종적으로 진 횟수 + 이긴 횟수 === n-1 번이면 순위가 확정된다.

bfs에서 무한루프가 걸리는거 같다..
합계: 40.0 / 100.0 나머지 시간초과

function solution(n, results) {
    const battle = [...Array(n + 1)].map(_ => new Set());

    results.forEach(([a, b]) => battle[a].add(b));
    // a win b, b win c => a win c
    for (var i = 1; i <= n; i++) {
        const q = [...battle[i]];
        while(q.length){
            const cur = q.shift();
            [...battle[cur]].forEach(v => q.push(v));
            battle[i].add(cur);
        }
    }
    var ans = 0;
    for (var i = 1; i <= n; i++) {
        const lose = battle.reduce((ac, v) => ac + (v.has(i) ? 1 : 0), 0);
        if (battle[i].size + lose === n - 1)
            ans++;
    }
    return ans;
}

최종 코드

결국 3중 for문으로 최적화

function solution(n, results) {
    const battle = [...Array(n + 1)].map(_ => Array(n + 1).fill(false));

    results.forEach(([a, b]) => battle[a][b] = true);
    for (var i = 1; i <= n; i++)
        for (var j = 1; j <= n; j++)
            for (var k = 1; k <= n; k++)
                if (battle[j][i] && battle[i][k])
                    battle[j][k] = true;

    var ans = 0;
    for (var i = 1; i <= n; i++){
        var cnt = 0;
        for(var j = 1; j <= n; j++)
            if(battle[i][j] || battle[j][i])
                cnt++;
        if(cnt === n-1)
            ans++;
    }
    return ans;
}

비슷한 문제

https://www.acmicpc.net/problem/2458