[Ava]Programmersランキング(グラフィック)

Programmers Lv 3ランキング

グラフ

level3

🔍 問題の説明

https://programmers.co.kr/learn/courses/30/lessons/49191
ボクシングの試合にはn人のボクサーが参加し、それぞれ1番からn番まで参加した.ボクシングの試合は1対1で行われ、A選手の実力がB選手より優れていれば、A選手はいつもB選手に勝つ.審判は与えられた試合の結果に基づいて選手をランキングしたいと思っている.しかし、いくつかの試合結果を失ったため、正確な順位はつけられなかった.
アスリートの数n,試合結果の2次元配列結果をパラメータとして与える場合は,正確に並べ替えられるアスリートの数を返すために解関数を記述してください.

せいげんじょうけん

選手の数は1名以上100名以下です.
試合結果は1個以上4500個以下であった.
その結果、各行[A,B]に並んでA選手がB選手に勝ったことを示す.
すべての試合の結果に矛盾はなかった.

I/O例

n = 5
results = [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]]
return = 2
2番選手は[1,3,4]選手に敗れ、5番選手が勝利したので4位だった.
5番は4位の2番に負けて5位だった

💡 に答える

int answer:正確にランキングできる選手数ArrayList<Integer>[] winList:1~n番の選手が優勝した選手リストArrayList<Integer>[] loseList:1~n番選手の選手名簿int getWinCnt(int idx,int n):idx選手が勝つ選手数を求めるbfs方法int getLoseCnt(int idx,int n):idx選手数を求めるbfs方法
BFSで解決しました.
この問題で求められるのは、正確にランキングできる選手の数です.
i番選手の順位を求めるには、すべての選手のi番選手が勝つか負けるかを知らなければならない.これはi番選手がn-1番の決闘を行うことを意味する.
すなわち、n名選手がいる場合、i番選手のwinCnt(이긴 횟수)、loseCnt(진 횟수)の和はn-1でなければならない.
まず、試合結果を保存する結果配列に移動します.
各選手の勝負結果はwinListloseListに保存されている.

for (int i = 0; i < results.length; i++) {
	int A = results[i][0];
	int B = results[i][1];
			
	winList[A].add(B); //A가 B선수를 이겼다.
	loseList[B].add(A); //B가 A선수에게 졌다.
}

そしてfor文でidx=1からidx=n番の選手にwincntとlosecntを求めた.
各cntは、bfsおよび上のwinListおよびloseListによって取得することができる.
求められたwinCnt+loseCntの和がn-1であれば、answerが1つ増加する.

💡 ソースコード

import java.util.*;

class Solution {
    static ArrayList<Integer>[] winList;
	static ArrayList<Integer>[] loseList;
    
    public int solution(int n, int[][] results) {
		int answer = 0;  //정확하게 순위를 매길 수 있는 선수
		
        winList = new ArrayList[n+1]; //1~n번  선수가 이긴 선수 리스트
        loseList = new ArrayList[n+1]; //1~n번 선수가 진 선수 리스트
        
        for (int i = 0; i <= n; i++) {
			winList[i] = new ArrayList<>();
			loseList[i] = new ArrayList<>();
		}
        
        //경기 결과 승패 저장
        for (int i = 0; i < results.length; i++) {
			int A = results[i][0];
			int B = results[i][1];
			
			winList[A].add(B); //A가 B선수를 이겼다.
			loseList[B].add(A); //B가 A선수에게 졌다.
		}
        
        
        for (int idx = 1; idx <= n; idx++) {
        	int winCnt = getWinCnt(idx, n);
        	int loseCnt = getLoseCnt(idx, n);

        	if(winCnt + loseCnt == n-1) answer++; 
            //이긴선수 + 진 선수 = n-1이면 모든 경기의 결과를 알수 있으므로 등수를 구할 수 있다.
		}

        return answer;
    }
	
    //idx 선수가 이긴 선수의 수를 구하는 bfs 메소드
	private static int getWinCnt(int idx,int n) {
		Queue<Integer> queue = new LinkedList<>();
		boolean[] visited = new boolean[n+1];
		int winCnt = 0;
		
		queue.add(idx);
		visited[idx]=true;
		
		while(!queue.isEmpty()) {
			int playerNum = queue.poll();
			
			for (int i = 0; i < winList[playerNum].size(); i++) {
				int tgtNum = winList[playerNum].get(i);
				if(visited[tgtNum]) continue;
				visited[tgtNum] = true;
				queue.add(tgtNum);
				winCnt++;
			}
		}
		return winCnt;
	}
	
    //idx 선수가 진 선수의 수를 구하는 bfs 메소드
	private static int getLoseCnt(int idx,int n) {
		Queue<Integer> queue = new LinkedList<>();
		boolean[] visited = new boolean[n+1];
		int loseCnt = 0;
		
		queue.add(idx);
		visited[idx]=true;
		
		while(!queue.isEmpty()) {
			int playerNum = queue.poll();
			
			for (int i = 0; i < loseList[playerNum].size(); i++) {
				int tgtNum = loseList[playerNum].get(i);
				if(visited[tgtNum]) continue;
				visited[tgtNum] = true;
				queue.add(tgtNum);
				loseCnt++;
			}
		}
		return loseCnt;
	}
}

結果

正確性テスト
試験1〉合格(0.25 ms,52.7 MB)
試験2〉合格(0.27 ms,52.2 MB)
試験3〉合格(0.62 ms,53.4 MB)
試験4〉合格(0.30 ms,52.1 MB)
試験5〉合格(2.84 ms,52.6 MB)
試験6〉合格(5.42 ms,53.7 MB)
試験7〉合格(12.77 ms,53.7 MB)
試験8〉合格(27.11 ms,57.2 MB)
試験9〉合格(28.51 ms,54.7 MB)
試験10〉合格(29.21 ms,55.3 MB)
採点結果
精度:100.0
合計:100.0/100.0