[프로그래머스] 순위

문제

순위

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

 

 

풀이

설명

정확하게 순위를 매길 수 있는 선수의 수를 구하는 문제입니다.

 

그래프 탐색을 통해 해결할 수 있습니다.

 

각 선수별로 이긴 선수와 진 선수에 대해 각각 그래프 탐색을 진행하며 카운트를 늘려갑니다.

카운트의 합이 n - 1이라면 해당 선수는 순위를 매길 수 있습니다.

 

예시 코드

class Player {
  constructor(id) {
    this.id = id;
    this.wins = [];
    this.loses = [];
  }
}

function solution(n, results) {
  const players = Array.from({ length: n + 1 }, (_, i) => new Player(i));
  let answer = 0;

  for (const [winner, loser] of results) {
    players[winner].wins.push(loser);
    players[loser].loses.push(winner);
  }

  const visited = Array(n + 1).fill(false);

  for (let i = 1; i <= n; i++) {
    visited.fill(false);

    const winCount = dfs(players[i], "wins");
    const loseCount = dfs(players[i], "loses");

    if (winCount + loseCount === n - 1) answer++;
  }

  return answer;

  function dfs(player, graph) {
    let cnt = 0;

    for (const opponentId of graph === "wins" ? player.wins : player.loses) {
      if (visited[opponentId]) continue;
      visited[opponentId] = true;

      cnt += 1 + dfs(players[opponentId], graph);
    }

    return cnt;
  }
}