🔎 순위

❓ 문제링크

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

📄 제출 코드

function solution(n, results) {
    let rank = [];
    for (var i = 0; i < n; i++) {
        rank[i] = new Array(n).fill(0);
    }

    for (var j = 0; j < results.length; j++) {
        let win = results[j][0]-1;
        let lose = results[j][1]-1;
        console.log(`win : ${win}, lose : ${lose}`)
        rank[win][lose] = 1;
        rank[lose][win] = -1;
    }
    console.log(rank);
    
    for (var i = 0; i < n; i++) {
        for (var j = 0; j < rank[i].length; j++) {
            for (var k = 0; k < rank[i].length; k++) {
                if (j == i || k == i) continue;
                if (rank[j][i] == 1 && rank[i][k] == 1) {
                    rank[j][k] = 1;
                } else if (rank[j][i] == -1 && rank[i][k] == -1) {
                    rank[j][k] = -1;
                }
            }  
        }
    }
    console.log(rank);
    var answer = 0;
    for (var i = 0; i < n; i++) {
        let cnt = 0;
        for (var j = 0; j < rank[i].length; j++) {
            if (rank[i][j] == 0) {
                cnt++;
            }
            if (j ==rank[i].length-1 && cnt == 1) answer++;
        }
    }
    
    
    return answer;
}

let n = 5;
let results = [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]];
console.log(solution(n, results));

처음에 문제를 보고, 어떻게 풀지 하고 고민하다가 일단 순위표를 만들어 봐야겠다고 생각했다.
그래서 rank라는 배열을 만들었고, 0으로 먼저 다 채우고, 이긴 경우 1, 진 경우 -1로 입력했다.

초기 rank값

[
  [ 0, 1, 0, 0, 0 ],
  [ -1, 0, -1, -1, 1 ],
  [ 0, 1, 0, -1, 0 ],
  [ 0, 1, 1, 0, 0 ],
  [ 0, -1, 0, 0, 0 ]
]

그런 다음 문제의 설명에 _2번 선수는 [1, 3, 4] 선수에게 패배했고, 5번 선수에게 승리했기 때문에 4위입니다. 5번 선수는 4위인 2번 선수에게 패배했기 때문에 5위입니다._라고 되있다.
즉, 2번선수가 1,3,4에게 졌고, 5번선수가 2번에게 졌으니 5번 선수는 1,2,3,4에게 진 게 됩니다.

위의 선 색끼리 비교를 해야한다.

[0,0]일 때, [0,0],[0,1], [0,2], [0,3], [0,4]
[1,0]일 때, [0,0],[0,1], [0,2], [0,3], [0,4]
[2,0]일 때, [0,0],[0,1], [0,2], [0,3], [0,4]
[3,0]일 때, [0,0],[0,1], [0,2], [0,3], [0,4]
[4,0]일 때, [0,0],[0,1], [0,2], [0,3], [0,4]

[0,1]일 때, [1,0],[1,1], [1,2], [1,3], [1,4]
[1,1]일 때, [1,0],[1,1], [1,2], [1,3], [1,4]
[2,1]일 때, [1,0],[1,1], [1,2], [1,3], [1,4]
[3,1]일 때, [1,0],[1,1], [1,2], [1,3], [1,4]
[4,1]일 때, [1,0],[1,1], [1,2], [1,3], [1,4]

이런 식으로 말이다.
[j,i][i,k]형식으로 비교하여 둘 다 값이 1이면 rank[j][k]값을 1, -1이면 -1로 변경.

[
  [ 0, 1, 0, 0, 1 ],
  [ -1, 0, -1, -1, 1 ],
  [ 0, 1, 0, -1, 1 ],
  [ 0, 1, 1, 0, 1 ],
  [ -1, -1, -1, -1, 0 ]
]

이렇게 된다.
간단하게 설명하자면, 0,1의 경우일 때 1인데, [1,i]에서 i가 4일때도 1이니까 [0,4]를 1로 변경한다.
즉, 1번선수가 2번선수를 이기는데, 2번선수가 5번선수를 이겼으니 1번선수가 5번도 이긴다는 거다.

다 변경 후 0의 개수가 자기 자신뿐인 배열이 있으면 answer에 +1을 해서 답을 도출했다.
(풀릴거 같아서 계속 붙잡다가 2시간넘게 걸렸다 ;)

🌏 플로이드 와샬

질문게시판이나 다른 풀이를 보면 플로이드 와샬로 풀면 간단하게 풀린다고 한다.

플로이드 와샬이란 '거쳐가는 정점'을 기준으로 최단거리를 구한다는 알고리즘이다.
하나의 정점을 출발점으로 해서 모든 정점가지의 최단경로를 구하는 알고리즘.
모든 각각의 정점을 출발점으로 해서 모든 정점까지 최단경로를 구하기 때문에 시간복잡도는 O(N³)이다.

참고 : https://taesung1993.tistory.com/50