문제

title: "코딩테스트 연습 - 순위"
image: "https://image.freepik.com/free-vector/landing-page-template-for-a-website_23-2147782747.jpg"
description: "n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다."
url: "https://school.programmers.co.kr/learn/courses/30/lessons/49191?language=java"

문제 풀이

문제 접근

  • 순위를 매길 수 있는 선수는 모든 선수와 대결을 한 선수? -> X
  • 모든 경기 결과를 배열에 정리하여 파악해보자.

    경기 결과 정리

    public static int[][] calGame(int n, int[][] results) {
      int[][] allGame = new int[n][n];
        
      // init allGame (7-none, 1-win, -1-lose)
      for (int i = 0; i < n; i++) {
          allGame[i][i] = 7; // none
      }
      for (int i = 0; i < n; i++) {
          allGame[results[i][0]-1][results[i][1]-1] = 1; // win
          allGame[results[i][1]-1][results[i][0]-1] = -1; // lose
      }
        
      return allGame;
  }
  • 결과 7 1 0 0 0
    -1 7 -1 -1 1
    0 1 7 -1 0
    0 1 1 7 0
    0 -1 0 0 7

    경기 결과 분석

  • 0이 없는 선수는 순위를 정확히 매길 수 있다.
  • 또한 그 선수들의 순위 기준으로 다른 선수들의 순위를 알 수도 있다.
  • 자신과 다른 모든 선수 간의 관계를 알 수 있는 선수만이 자신의 정확한 순위를 알 수 있다.
    • 내가 만약 4위에게 졌다면, 그에게 이긴 3명은 못이긴다.

간단한 수도 코드 정리

1 Initialize the allGame matrix:
Create an n x n matrix initialized with 0.
For each [A, B] in results:
    Mark A beats B as 1
    Mark B loses to A as -1.

2 Apply Floyd-Warshall algorithm:
For each k from 0 to n-1:
    For each i from 0 to n-1:
        For each j from 0 to n-1:
            If i beats k and k beats j, then i beats j.
            If i loses to k and k loses to j, then i loses to j.

3 Count players with certain ranks:
Initialize count to 0.
For each player i from 0 to n-1:
    Check if i has results against all other players.
    If yes, increment count.

4 Return the count.

풀이 코드

import java.util.*;

class Solution {
    public int solution(int n, int[][] results) {
        int[][] allGame = calGame(n, results);

        // 플로이드-워셜 알고리즘을 통해 모든 선수 간의 승패 정보를 갱신
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (allGame[i][k] == 1 && allGame[k][j] == 1) {
                        allGame[i][j] = 1;
                    }
                    if (allGame[i][k] == -1 && allGame[k][j] == -1) {
                        allGame[i][j] = -1;
                    }
                }
            }
        }

        // 선수들의 승패 정보가 확실한 선수의 수를 셉니다.
        int answer = 0;
        for (int i = 0; i < n; i++) {
            boolean certain = true;
            for (int j = 0; j < n; j++) {
                if (i != j && allGame[i][j] == 0) {
                    certain = false;
                    break;
                }
            }
            if (certain) {
                answer++;
            }
        }
        
        return answer;
    }
    
    public static int[][] calGame(int n, int[][] results) {
        int[][] allGame = new int[n][n];
        
        // init allGame (0-unknown, 1-win, -1-lose)
        for (int i = 0; i < n; i++) {
            allGame[i][i] = 0; // self match (irrelevant)
        }
        for (int i = 0; i < results.length; i++) {
            allGame[results[i][0] - 1][results[i][1] - 1] = 1; // win
            allGame[results[i][1] - 1][results[i][0] - 1] = -1; // lose
        }
        
        return allGame;
    }
}