프로그래머스 - 순위

문제 출처: https://programmers.co.kr/learn/courses/30/lessons/49191

코딩테스트 연습 - 순위

 

문제의 핵심은 i번 선수의 순위를 확실히 알 수 있는 방법은, i번 선수의 경기 결과가 n-1개 있으면 확실히 그 순위를 알 수 있다.

물론 그렇지 않더라도 n-1개의 결과를 가지고 있는 선수와 연결된 또 다른 선수의 결과 또한 알 수 있다.

 

필자는 이 문제를 2가지 방식으로 해결했다. 첫 번째는 특정 선수가 이긴 횟수+진 횟수 = n-1개 이면 순위를 구할 수 있다.

예제 테케를 보면, 

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

2번 선수는 1번 이기고, 3번 졌으므로 총 4번의 경기 결과를 확인할 수 있다. 그러므로 4등이라는 순위 파악이 가능하다.

5번은 경기 결과는 1개뿐이지만 2번이 4등이라는 결과를 통해 5등을 유추할 수 있다.

 

이긴 횟수, 진 횟수를 간단히 그래프를 통해 확인이 가능하다. 이겼으면 부모 노드, 졌으면 자식 노드를 설정해놓으면 된다.

다시, 5번 노드를 확인하면 부모노드(진 횟수)로 1,2,3,4가 있다는 것을 확인이 가능하고 자식 노드(이긴 횟수)는 없으므로 총 4개의 경기 결과를 유추할 수 있다.

 

	for(int i=0;i<results.length;i++){
            int win=results[i][0]-1;
            int lose = results[i][1]-1;
            list[win].add(lose);
        }
        //부모 찾기
        int idx=0;
        while(idx<n){
            parentCnt=0;

            for(int i=0;i<n;i++){
                v= new boolean[n];
                if(i!=idx){
                    v[i]=true;
                    searchParent(i,idx);

                }

            }
            parents[idx]=parentCnt;
            idx++;
        }

        //자식 찾기
        for(int i=0;i<n;i++){
            v = new boolean[n];
            manyWin=0;
            v[i]=true;
            hasWin(i);
            winCnt[i]=manyWin;
        }

 

부모 노드의 배열인 parents와 자식 노드의 배열인 winCnt를 통해 각각 인덱스의 합이 n-1이면 순위를 유추할 수 있다.

 

다음 방식으로는 Floyd-washall방식을 사용했다.

기존 플로이드 워셔 코드는 거리를 갱신하는 방식이지만 경유지를 통해 특정 노드에 도달 할 수 있으면 갱신이 아니라 1로 설정하였다.

 

      for(int k=0;k<n;k++){
            for(int i=0;i<n;i++){
                if(i==k)continue;
                for(int j=0;j<n;j++){
                    if(i==j || k==j)continue;
                    if(map[i][k]+map[k][j]<map[i][j])
                        map[i][j]=1;
                }
            }
        }

 

그리고 각각 행 열의 합과 겹치는 부분을 제외해서 그 합이 n-1이면 순위를 파악할 수 있다.