[프로그래머스] 그래프 - 순위

그래프의 개념보다는 set의 개념을 이용하여 문제를 풀었다..

 

블로그 https://velog.io/@ajufresh/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%88%9C%EC%9C%84-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-Java

[프로그래머스] 순위 문제풀이 (Java)

를 참고하여 코드는 내가 작성한 것이다.

 

package algorithmStudy;

import java.util.*;

class Player{
	Set<Integer> win=new HashSet<>();	//player한테 이긴사람
	Set<Integer> lose=new HashSet<>();	//player 진사람
}

public class graph2 {
    static int solution(int n, int[][] results) {
        int answer = 0;
        
        Player[] players=new Player[n+1];
        //player배열 초기화
        for(int i=0;i<n+1;i++) {
        	players[i]=new Player();
        }
        
        for(int i=0;i<results.length;i++) {
        	int winner=results[i][0];
        	int loser=results[i][1];
        	
        	//결과를 추가
        	players[loser].win.add(winner);
        	players[winner].lose.add(loser);
        	//winner를 이긴사람들을 players[loser].win에 추가
        	players[loser].win.addAll(players[winner].win);
        	//loser한테 진사람들을 players[winner].lose에 추가
        	players[winner].lose.addAll(players[loser].lose);
        }
        
        for(int i=results.length-1;i>=0;i--) {
        	int winner=results[i][0];
        	int loser=results[i][1];
        	
        	//winner를 이긴사람들을 players[loser].win에 추가
        	players[loser].win.addAll(players[winner].win);
        	//loser한테 진사람들을 players[winner].lose에 추가
        	players[winner].lose.addAll(players[loser].lose);
        }
        
        for(int i=0;i<=n;i++) {
        	if(players[i].win.size()+players[i].lose.size() ==n-1)
        		answer++;
        }
        
        return answer;
    }
    
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int n=5;
		int[][] results= {{4,3},{4,2},{3,2},{1,2},{2,5}};
		System.out.println(solution(n,results));
	}

}

d한방향으로만 탐색하면.. 혹시 비는 부분이 있을까 싶어서 반대 방향으로도 탐색햇다.

 

한 방향 탐색시 30점이었고, 양 방향 탐색 추가시 60점.. 이외는 왜 틀린지 모르겠다.. 

(테스트 케이스 공개해주세여 ㅠㅠ)