[JavaScript] Programmers 순위 (JS)

순위

📚 문제 설명

n 명의 권투 선수가 있다. 선수들의 전적이 주어졌을 때,
등수를 알 수 있는 선수는 몇명인가?

이 문제가 이해가 되지 않는경우에는 이 문제와 거의 똑같은 백준 키 순서 문제 설명을 읽으면 도움이 될 것이다.

👨🏻‍💻 풀이 과정

앞에서 말했던 것처럼 이 문제는 이전에 풀었던 문제와 똑같다고 봐도 될 정도로 유사하다.
따라서 이 문제 또한 Floyd-Warshall로 푸는 방식과 DFS를 이용하는 방식 2가지로 풀 수 있다.

코드 로직은 거의 완벽하게 똑같기 때문에 굳이 다시 설명하지 않고 코드와 주석만 보여주겠다.

💡1차 제출 코드 (DFS)

DFS 풀이 전체 코드

    function solution(n, results) {
		// 정방향 트리
        let GoStraight = Array.from({length: n}, _ => []);
      
        // 역방향 트리
        let GoReverse = Array.from({length: n}, _ => []);
      
        // 연결된 노드 갯수를 저장 할 배열.
        let MapCounter = Array.from({length: n}, _ => 0);
      
        // 트리 생성.
        results.forEach(v => {
            const [Start, End] = v;
            GoStraight[Start - 1].push(End);
            GoReverse[End - 1].push(Start);
        });

      	//DFS 함수
        const DFS = (tree, now, visited) => {
            visited[now] = true;
            MapCounter[now] += 1;
            if (!tree[now]) return;
            for (let i = 0; i < tree[now].length; i++) {
                const Next = tree[now][i] - 1;
                if (!visited[Next]) {
                    DFS(tree, Next, visited);
                }
            }
        };
	
      	// DFS함수를 tree의 각각의 노드마다 실행
        const Go = (tree) => {
            for (let i = 0; i < n; i++) {
                let visited = Array.from({length: n}, _ => false);
                DFS(tree, i, visited);
                visited = visited.map(_ => false);
            }
        };
      	// 정방향으로 DFS 실행
        Go(GoStraight);
      	// 역방향으로 DFS 실행
        Go(GoReverse);

      	// reduce 함수를 이용해 n보다 큰 값의 갯수를 세준다.
        return (MapCounter.reduce((acc,cur) => {
            if (cur > n) {
                return acc + 1;
            }else return acc;
        }, 0));

    }

💡2차 제출 코드 (Floyd-Warshall)

    function solution(n, results) {
      	// 각각의 노드 연결관계를 위한 2차원 배열.
        let tables = Array.from({length: n}, _ => Array.from({length: n}, _ => false));
      	// 나와 연결된 노드의 갯수를 저장하는 배열.
      	// TableCounter[i] : i와 연결된 노드의 갯수.
        let TableCounter = Array.from({length: n}, _ => 0);

		// 연결 관계 체크.
        for (const [Win, Lose] of results) {
            tables[Win - 1][Lose - 1] = true;
        }
      
      	// Floyd-Warshall 을 위한 3중 for문.
        // 중간 지점.
        for (let i = 0; i < n; i++) {
            // 시작 지점.
            for (let j = 0; j < n; j++) {
                // 끝 지점.
                for (let k = 0; k < n; k++) {
                  	// j - i 가 연결 되고 i - k 가 연결되면 j - k 도 연결된다.
                    if (tables[j][i] && tables[i][k]) {
                        tables[j][k] = true;
                    }
                }
            }
        }

      	// tables 배열을 돌며 연결 가능한 선의 갯수 체크.
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < n; j++) {
                if (tables[i][j] || tables[j][i]) {
                    TableCounter[i] += 1;
                }
            }
        }
      	// 자신을 제외한 n - 1개의 노드와 연결이 가능하면 순위를 알 수 있다.
        return (TableCounter.filter(v => v >= n - 1).length);
    }

🧐 후기

기존에 풀었던 문제와 거의 완벽하게 똑같은 문제라 복습 느낌으로 풀었던 문제였다.