[프로그래머스(Programmers)][자바(java)] (Lv3) 순위

 

programmers.co.kr/learn/courses/30/lessons/49191

코딩테스트 연습 - 순위

 

 

문제 설명

n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다.

선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• 선수의 수는 1명 이상 100명 이하입니다.
• 경기 결과는 1개 이상 4,500개 이하입니다.
• results 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미입니다.
• 모든 경기 결과에는 모순이 없습니다.

 

입출력 예

n	results	return
5	[[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]]	2

입출력 예 설명

2번 선수는 [1, 3, 4] 선수에게 패배했고 5번 선수에게 승리했기 때문에 4위입니다.
5번 선수는 4위인 2번 선수에게 패배했기 때문에 5위입니다.

 

 

문제 풀이

import java.util.Arrays;
import java.util.HashMap;

public class Solution {
	
	public boolean[][] floydWarshall( boolean c[][], boolean e[][], int n ) {
		int i, j, k;
		for( i = 0; i < n; i++ ) 
			for( j = 0; j < n; j++ )
				if( e[i][j] )
					c[i][j] = true;
		for( k = 0; k < n; k++ )
			for( i = 0; i < n; i++ )
				for( j = 0; j < n; j++ )
					if( c[i][k] && c[k][j] )
						c[i][j] = true;
		return c;
	}
	
	public int solution(int n, int[][] results) {
        int i, j, l = results.length;
        boolean e[][] = new boolean[n][n];	// edge ( is adjacent ? )
        boolean c[][] = new boolean[n][n];	// connected ( is connected ? )
        for( i = 0; i < l; i++ )
        	e[--results[i][0]][--results[i][1]] = true;
        c = floydWarshall( c, e, n );
        int p[] = new int[n];				// priority ( bigger num, higher rank )
        for( i = 0; i < n; i++ )
        	for( j = 0; j < n; j++ )
        		if( c[i][j] )
        			p[i]++;
        Arrays.sort( p );
        HashMap<Integer, Integer> hm = new HashMap<>();
        for( i = 0; i < n; i++ ) {
        	if( hm.containsKey( p[i] ) )
        		hm.replace( p[i], hm.get( p[i] ) + 1 );
        	else
        		hm.put( p[i], 1 );
        }
        int ans = 0;
        for( i = 0; i < n; i++ )
        	if( p[i] == i && hm.get(p[i]) == 1 )
        		ans++;
        return ans;
    }

}

 

* 그래프

‘이긴 사람 -> 진 사람’ 방향으로 연결된 ‘방향 그래프’ 라고 가정 한다.

인접 행렬 생성 시 정점번호 -1 한다. ( 인덱스 0부터 사용하기 위해 )

in-degree( 방향 그래프에서 어떤 한 정점으로 들어오는 edge의 개수 )가 없는 노드가 비교적 상위( 순위가 높은 ) 노드라고 볼 수 있다.

하지만 정확한 순위를 모르는 노드들이 있으므로 항상 최상위 노드를 구할 수 있는 것은 아니다.

그러므로 모든 쌍 최단 경로 알고리즘을 응용하여 각 노드에 연결된 노드들의 개수를 구해 배열 p ( int[] )에 넣음

한 노드에서 다른 노드로 갈 수 있는 경로가 있다면 연결된 노드이다.

각 노드에 연결된 노드들의 개수는 각 사람보다 순위가 낮은 사람들의 수와 같다.

즉 연결된 노드들의 개수가 많을수록 높은 순위이다.

배열 p를 정렬하고, 각 값을 map에 넣는다. ( key : p[i], value : cnt )

배열 p에서 i와 p[i]이 같으며, map에서 key가 p[i]인 값이 1일 때( 중복이 없을 때 ) 정확한 순위를 매길 수 있다.