[프로그래머스] 순위 자바(Java) 풀이 및 해설

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

프로그래머스

 

풀이 방법

우선 경기 결과로 확실하게 순위를 알 수 있는 경우는 다음과 같다.

 

사람이 N명일때

나를 이긴 사람들 수와 나에게 진 사람들의 수가 N-1일때, 나의 순위는 (나를 이긴 사람들 수 + 1)위 이다.

 

그런데 여기서 더 생각해볼 수 있는 부분은 다음과 같다.

• 나를 이긴 사람들 (간접적으로 이긴 사람들이다.)
  • 내가 진 사람들을 이긴 사람들 또한 나를 이긴 사람들이다.
  • 내가 진 사람을 이겼다는것은 나를 이길 수 있기 때문이다.
• 나에게 진 사람들 (간접적으로 진 사람들이다.)
  • 내가 이긴 사람에게 진 사람들 또한 나에게 진 사람들이다.
  • 내가 이긴 사람에게 졌다는건 내가 이길 수 있는 상대이기 때문이다.

 

우선 주어진 결과들을 통해 내가 이긴 사람들과 내가 진사람들을 Set로 저장한다.

 

내가 간접적으로 이긴 사람들은 

나에게 진사람들의 진 사람들을 타고타고 들어가면 된다.

 

내가 간접적으로 진 사람들은

나를 이긴 사람들의 이긴 사람들이다.

 

전체 코드

import java.util.*;
class Solution {
    
    public class Info {
        
        Set<Integer> win; // 내가 이긴 사람들
        Set<Integer> lose; // 내가 진 사람들
        
        public Info() {
            this.win = new HashSet<Integer>();
            this.lose = new HashSet<Integer>();
        }
    }
    
    public Set<Integer> findChildLoser(Set<Integer> childLoser, Info[] info, int i) {
        
        for(Integer child : info[i].win) {
            
            if (!childLoser.contains(child)) {
                childLoser.add(child);
                findChildLoser(childLoser, info, child);
            }
            
        }
        return childLoser;
    }
    
    public Set<Integer> findParentWinner(Set<Integer> parentWinner, Info[] info, int i) {
        for(Integer parent : info[i].lose) {
            
            if (!parentWinner.contains(parent)) {
                parentWinner.add(parent);
                findParentWinner(parentWinner, info, parent);
            }
            
        }
        return parentWinner;
    }
    
    public void update(Info[] info) {
        
        
        // A와 B가 싸웠을때
        // A가 이겼다면 B에게 진 사람들도 A가 이긴거랑 동일함.   
        for(int i=1; i<info.length; i++) {
            
            // i에게 진 사람들 childLoser
            Set<Integer> childLoser = new HashSet<Integer>();
            findChildLoser(childLoser, info, i);
            
            // i는 childLoser들도 이긴것이다.
            for(Integer child : childLoser) {
                info[i].win.add(child);
            }
            
            // i에게 이긴 사람들 parentWinner
            Set<Integer> parentWinner = new HashSet<Integer>();
            findParentWinner(parentWinner, info, i);
            
            // i는 parentWinner에게도 진것이다.
            for(Integer parent : parentWinner) {
                info[i].lose.add(parent);
            }
            
        }
        
        
    }
    
    public int solution(int n, int[][] results) {
        int answer = 0;
        
        Info[] info = new Info[n+1];
        for(int i=1; i<=n; i++) {
            info[i] = new Info();
        }
        
        for(int i=0; i<results.length; i++) {
            
            int winner = results[i][0];
            int loser = results[i][1];
            
            info[winner].win.add(loser);
            info[loser].lose.add(winner);
            
            
        }
        
        update(info);
        
        for(int i=1; i<=n; i++) {
            System.out.println(info[i].win.size() + " " + info[i].lose.size());
            if (info[i].win.size() + info[i].lose.size() == n-1)
                answer++;
        }
        
        return answer;
    }
}

 

+ 플로이드 와샬 알고리즘 코드

다른 코드들을 보니 플로이드 와샬을 사용했다.

이 문제를 보고 플로이드 와샬을 사용할 생각을 하다니, 똑똑한 사람들은 많다.

 

방법은 다음과 같다.

나를 제외한 N-1명의 선수와의 경기 결과를 안다면 나의 순위를 알 수 있다.

내가 6명의 선수가 있을때 3승 2패로 N-1명의 선수 결과를 안다면

나의 순위는 3승했으니 4위인것을 알 수 있다. 

 

전체 코드

import java.util.*;
class Solution {
    
    public int solution(int n, int[][] results) {
        int answer = 0;
        
        int graph[][] = new int[n+1][n+1];
        for(int i=0; i<results.length; i++) {
            graph[results[i][0]][results[i][1]] = 1;
            graph[results[i][1]][results[i][0]] = -1;
        }
        
        for(int i=1; i<=n; i++) { // i 선수
            for(int j=1; j<=n; j++) { // j 선수
                for(int k=1; k<=n; k++) { // 거치는 k 선수
                    if (graph[i][k] == 1 && graph[k][j] == 1) {
                        // i가 k를 이기고, k가 j를 이긴다면
                        graph[i][j] = 1; // i는 j를 이기고
                        graph[j][i] = -1; // j는 i에게 진다.
                    }
                    
                    if (graph[i][k] == -1 && graph[k][j] == -1) {
                        // i가 k에게 지고, k가 j에게 진다면
                        graph[i][j] = -1; // i는 j에게 진다.
                        graph[j][i] = 1; // j는 i에게 이긴다. 
                    }
                }
            }
        }
        
        for(int i=1; i<=n ; i++) {
            int count = 0;
            
            for(int j=1; j<=n; j++) {
                if (graph[i][j] != 0)
                    count++;
            }
            
            if (count == n-1)
                answer++;
        }       
        
        return answer;
    }
}