[프로그래머스]순위

📖 문제

level3 순위

✏️ 나의 풀이

처음 이 문제를 보고 당시에는 알고리즘 이름이 기억이 나지 않았지만, 플로이드 와샬 알고리즘이 떠올랐다.

하지만, 예전에 공부했던 알고리즘이여서 다시 공부하게 되었다.

플로이드 와샬 알고리즘

이 알고리즘은 다익스트라 알고리즘과 유사한 알고리즘이다.

다익스트라 알고리즘은 하나의 정점에서 최단거리의 정점을 구하는 알고리즘이라면 플로이드 와샬 알고리즘은 모든 정점끼리의 최단거리를 구하는 알고리즘이다.

이렇게 된 양방향 그래프가 있다고 가정하자.

그럼 이를 인접행렬로 표현하면 아래와 같이 된다.

이럼 이제 모든 준비는 끝났다.

이제 중간노드를 선택해 해당 노드를 중간노드로 하여 다른 두 노드가 만날 수 있다면 이에 대한 최단 거리를 표에 새로 업데이트 시켜주면 된다.

1번 노드를 중간노드로 선택하였으면, 2-1-5, 2-1-4 이렇게 1번 노드를 거쳐 2번과 5번, 2번과 4번 노드로 가는 거리를 알 수 있게 된다.

이를 표에 업데이트 시켜준다. 그럼 아래와 같은 표로 변하게 된다.

이렇게 계속해서 반복해 최종적으로 모든 노드에 대한 최단 거리를 구해주면 되는 알고리즘이다.

문제에 적용

내가 푼 방식을 간단히 이야기하면,

먼저 i가 j를 이기는 경우를 먼저 찾아 주었다.

그리고 j가 이긴 k를 찾아 arr[i][k]와 arr[k][j]를 업데이트 시켜주었다.

이게 끝이다. 이렇게만 이야기하니 굉장히 간단한 문제인데, 나는 몇시간 동안 삽질을 계속했다…

for (let i = 1; i < array.length; i++) {
      for (let j = 1; j < array[i].length; j++) {
        if (i === j) continue;
        if (array[i][j] === null || array[i][j] === "lose") continue;
        let isUpdate = false;
        for (let k = 1; k < array[j].length; k++) {
          if (
            array[j][k] === null ||
            array[j][k] === "lose" ||
            array[i][k] === "win"
          )
            continue;
          array[i][k] = "win";
          array[k][i] = "lose";
          isUpdate = true;
        }
        if (isUpdate) i = 1;
      }
    }

참고로 나는 초기값을 null로 선언하고 이긴경우를 win, 진 경우를 lose 로 작성하였다.

코드를 보면 첫번째 i와 두번째 반복문의 j는 [i, j] 의 i와 j다.(i가 j를 이겼다.)

그래서 array[i][j]가 win일 경우만 [j, k]를 찾아주었다.

[j, k] 가 win 이고, [i, k] 가 null 인 경우만을 찾아주고, [i, k]를 토대로 업데이트 시켜주었다.

[i, k] 가 win 인 경우 이는 이미 표에 업데이트 준것이기에 굳이 동일한 작업을 할 필요가 없기에 continue를 해주었다.

그리고 만일, 표가 업데이트 되었다면 isUpdate 변수를 true로 만들어 준다.

그리고 k가 모든 반복문이 끝나고 isUpdate 변수가 true인 경우 i=1로 할당해준다.

처음에 이 때문에 테스트케이스 2번에서 막혔는데, 처음에는 j=1로 할당해주었다.

내 생각에는 [i, j, k]의 값이 변경된것이기에 중간 값인 j가 초기화되면 된다고 생각했지만, k=1에서 표가 업데이트 되었다면 처음부터 다시 확인할 필요가 있다고 생각했다.

그렇기에 표가 업데이트 되었다면 i=1 로 변경해 위 작업을 처음부터 진행한다.

마지막으로 array[i]에 null이 존재하지 않다면 이는 모든 경기의 값을 알고있는것으로 판단되기에 순위를 알 수 있다.

return array.filter((v, i) => {
  if (i === 0 || v.some((e) => e === null)) return false;
  return true;
}).length;

null이 포함되지 않은 행의 갯수를 구해 반환해주었다.

👩‍💻 코드

function solution(n, results) {
    var answer = 0;
    const array = new Array(n + 1)
      .fill(0)
      .map((_) => new Array(n + 1).fill(null));
    for (let i = 0; i < n + 1; i++) {
      array[0][i] = 0;
      array[i][0] = 0;
      array[i][i] = 0;
    }
    for (let i of results) {
      const [winner, loser] = i;
      array[winner][loser] = "win";
      array[loser][winner] = "lose";
    }
    for (let i = 1; i < array.length; i++) {
      for (let j = 1; j < array[i].length; j++) {
        if (i === j) continue;
        if (array[i][j] === null || array[i][j] === "lose") continue;
        let isUpdate = false;
        for (let k = 1; k < array[j].length; k++) {
          if (
            array[j][k] === null ||
            array[j][k] === "lose" ||
            array[i][k] === "win"
          )
            continue;
          array[i][k] = "win";
          array[k][i] = "lose";
          isUpdate = true;
        }
        if (isUpdate) i = 1;
      }
    }
    return array.filter((v, i) => {
      if (i === 0 || v.some((e) => e === null)) return false;
      return true;
    }).length;
  }