99클럽 코테 스터디 25일차 TIL / [프로그래머스] 순위

오늘의 학습 키워드

---

플로이드-와샬

문제

---

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

• 플랫폼: 프로그래머스
• 문제명: 순위
• 난이도: Lv3

풀이

---

class Solution {
    public int solution(int n, int[][] results) {
        int[][] rank = new int[n + 1][n + 1];
        
        for(int[] result : results) {
            rank[result[0]][result[1]] = 1;
            rank[result[1]][result[0]] = -1;
        }
        
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                for(int k=1; k<=n; k++) {
                    if(rank[i][k] == 1 && rank[k][j] == 1) {
                        rank[i][j] = 1;
                        rank[j][i] = -1;
                    }
                    
                    if(rank[i][k] == -1 && rank[k][j] == -1) {
                        rank[i][j] = -1;
                        rank[j][i] = 1;
                    }
                }
            }
        }
        
        int answer = 0;
        for(int i=1; i<=n; i++) {
            int cnt = 0;
            for(int j=1; j<=n; j++) {
                if(rank[i][j] != 0) {
                    cnt++;
                }
            }
            if(cnt == n-1) {
                answer++;
            }
        }
        
        return answer;
    }
}

접근

• A 선수가 B 선수를 이긴다 → B 선수가 C 선수를 이긴다 ⇒ A 선수가 C 선수를 이긴다로 이어집니다.
  • 이처럼 경기 결과가 주어지지 않았더라도, 이행적으로 승/패를 결정할 수 있습니다.
  • 따라서, 추론 가능한 모든 승패까지 고려하기 위해 플로이드-와샬 알고리즘을 활용합니다.

    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            for(int k=1; k<=n; k++) {
                if(rank[i][k] == 1 && rank[k][j] == 1) {
                    rank[i][j] = 1;
                    rank[j][i] = -1;
                }
                
                if(rank[i][k] == -1 && rank[k][j] == -1) {
                    rank[i][j] = -1;
                    rank[j][i] = 1;
                }
            }
        }
    }

• 정확하게 순위를 매길 수 있는 선수는 자신을 제외한 나머지 모든 선수들과의 승패가 결정되어야 합니다.
  • 즉, n명의 선수가 있을 때 n-1명의 선수와 승/패가 결정되어야 한다는 것입니다.

    for(int i=1; i<=n; i++) {
        int cnt = 0;
        for(int j=1; j<=n; j++) {
            if(rank[i][j] != 0) {
                cnt++;
            }
        }
        if(cnt == n-1) {
            answer++;
        }
    }

소요 시간

1시간 30분