[JAVA] 순위(코딩테스트 고득점 Kit [그래프]) - LEVEL3

📂문제 설명

 

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위입니다.

 

---

📂아이디어 및 알고리즘(문제 풀이)

• 문제 접근
  • 복서의 확실한 순위를 알기 위해서는 어떤 선수에게 이겼는지 졌는지에 대한 정보가 우선적으로 필요하다.
  • 그래서 Boxer라는 class를 만들어 누구에게 졌는지 이겼는지에 대한 정보를 저장해야한다 생각했다.
  • 그리고 확실한 순위는 N명이 있을때 N-1명에 대한 승,패 정보를 전부 알고있어야 한다.
  • 제일 중요한건 내가 상대방을 이겼을때 그 사람이 이긴사람들도 다 이긴다는 것과 내가 졌을때는 그 사람을 이겼던 사람들에게 진 거와 마찬가지다.
  • 이를 토대로 문제를 풀어나갔다. 
• 문제 풀이
  • Boxer라는 클래스를 만들어 HashSet을 이용해 중복을 제외하고 win,lose 정보를 저장할 수 있도록 만들었다.
  • 그래프를 만들기 위해 ArrayList<Boxer> boxers 를 생성했다.
  • 복서의 수만큼 index의 번호를 부여하여 그래프 틀을 만들었다.
  • results의 값들로 복서들 마다 누구에게 이겼는지 졌는지의 정보를 넣어주었다.
    
    • 선수들 마다 HashSet<Integer> winSet을 만들어서 내가 이긴 선수들에게 패배한 선수들을 찾아서 넣어준다.
    • winSet.add( [내가 이긴선수].Win의 list )를 추가 해주는 것이다. 
    • 그리고 HashSet<Integer> loseSet을 만들어서 위와 똑같이 내가 진 선수들에게 승리한 선수들을 찾아서 추가해준다.
    • loseSet.add( [내가 진 사람].Lose의 list )를 추가 해준다.
    • 마지막에 해당 복서에 중복을 제외하고 winSet 과 loseSet을 넣어준다.
  • 모든 선수에 대한 정보를 넣었을때 ((boxer.Win.size() + boxer.Lose.size()) == N-1)을 가지게 된 선수를 count 해주어 출력한다.  

 

📂소스 코드

import java.util.ArrayList;
import java.util.HashSet;
class Solution {

        static class Boxer{
    	int code;
    	
    	HashSet<Integer> Win = new HashSet<Integer>();
    	HashSet<Integer> Lose = new HashSet<Integer>();
    	
    	public Boxer(int code) {
    		this.code=code;
    	}
    }

    public static int solution(int n, int[][] results) {
	        int answer = 0;
	        ArrayList<Boxer> boxers = new ArrayList<>();
	        
	        //그래프 구현
	        for(int i=0;i<=n;i++) {
	        	boxers.add(new Boxer(i));
	        }
	        
	        //순위는 1~n 순위 까지 존재 ===> index마다 누구에게 지고 이겼는지를 따로 저장 해둔다.  
	        for(int[] index : results) {
	        	int win = index[0];
	        	int lose = index[1];	        	
	        	boxers.get(win).Win.add(lose); //이긴 기록
	        	boxers.get(lose).Lose.add(win);	//진 기록  	
	        }
	        
	        //확실히 결과를 알 수 있는 선수 
	        	for(int i=1;i<=n;i++) {	        		
	        		Boxer boxer = boxers.get(i);
	        		
	        		HashSet<Integer> winSet = new HashSet<Integer>();
	        		
	        		for(Integer win : boxer.Win) { //내가 이긴사람들은 그 사람들이 이긴 사람도 내가 이긴겨 
	        			for(Integer w : boxers.get(win).Win) {
	        				winSet.add(w);
	        			}
	        		}
	        		boxer.Win.addAll(winSet); //중복 제외하고 내가 이긴사람들이 이긴사람들을 추가!! 

	        		HashSet<Integer> loseSet = new HashSet<Integer>();
	        		
	        		for(Integer lose : boxer.Lose) { //내가 진 사람은 그 사람이 진 사람한테도 진겨  
	        			for(Integer l : boxers.get(lose).Lose) {
	        				loseSet.add(l);
	        			}
	        		}
	        		boxer.Lose.addAll(loseSet); //중복 제외하고 내가 이긴사람들이 이긴사람들을 추가!! 	        		
	        	}
	        	        
	        //확실한 선수를 통해 얻을 수 있는 결과!! 
	        for(Boxer box : boxers) {
	        	int size = box.Win.size() + box.Lose.size();
	        	if(size == (n-1)) answer++;
	        }
	        return answer;
	}
    
}