[프로그래머스] 순위 (javascript)

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

프로그래머스

 

🤔 해결방법

1. 승자 (winner)와 패자 (loser)를 확인하여 graph 생성

2. 플로이드-워셜 알고리즘을 사용하여 모든 선수 쌍 (i, j)에 대해 선수 i가 선수 j를 이길 수 있는지 확인

3. 승패가 확정된 경우만 찾아서 반환

 

 

🔑 풀이

문제를 읽어보니 어떻게 풀어야할 지 감도 안잡혀서 바로 구글링을 했다😅

모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 사용하는 플로이드-워셜 알고리즘 문제다.

 

먼저 결과 (results) 배열을 반복하면서 승자 (winner)와 패자 (loser)를 확인하여 이기면 true를 넣는 graph를 만든다.

그리고 플로이드-워셜 알고리즘을 사용하여 모든 선수 쌍 (i, j)에 대해 선수 i가 선수 j를 이길 수 있는지 확인한다.
i가 k를 이기고, k가 j를 이기면 (graph[i][k] && graph[k][j]) i가 j를 이길 수 있다. (graph[i][j] = true)

 

그 다음엔 각 선수에 대해 승패가 확정된 경우를 찾는다.
만약 i에 대해서 승리하거나 패배한 선수의 수가 n-1 (자기 자신을 제외한 모든 선수)이면 그 선수의 순위가 확정되었다고 할 수 있으므로 answer +1 을 해준다.
따라서 최종적으로 answer에 저장된 값을 출력하면 된다.

function solution(n, results) {
    // 그래프 생성
    let graph = [...Array(n + 1)].map(() => Array(n + 1).fill(false));
    for (let i = 1; i <= results.length; i++) {
      for (let [winner, loser] of results) {
        graph[winner][loser] = true;
      }
    }

    // 플로이드 워셜 알고리즘
    for (let k = 1; k <= n; k++) {
      for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= n; j++) {
          if (graph[i][k] && graph[k][j]) {
            graph[i][j] = true;
          }
        }
      }
    }

    let answer = 0;

    // 승패가 확정된 선수 찾기
    for (let i = 1; i <= n; i++) {
      let count = 0;
      for (let j = 1; j <= n; j++) {
        if (graph[i][j] || graph[j][i]) count++;
      }
      if (count === n - 1) answer++;
    }
    return answer;
  }

매주 새로운 알고리즘을 알게 되는 것 같다.🤪

플로이드-워셜 알고리즘 구현 부분이 3중 for문이라 시간 복잡도가 꽤 클 것 같았다.

찾아보니 시간 복잡도가 O(n^3)이라서 그래프의 크기가 작아 세제곱 시간 알고리즘을 적용해도 문제가 풀릴 때만 사용할 수 있다고 한다.

알아두자..!