프로그래머스 - 49191 - 순위 - Java

프로그래머스 -49191 - 순위 문제

문제

문제 푼 흔적

설명

설명을 읽어보면, 2 차원 배열로

index 0 ⇒ 이긴사람
index 1 ⇒ 진 사람
이렇게 주어진다.


승패에 관련된 정보를 전부 주어지는 것이 아닌
일부분이 주어지는데, 이를 통해 승패를 알 수 있는 사람이
몇명인지 맞추는 것이다.


이를 위해서
몇명을 이겼고 몇명에게 졌는지 정확히
아는 경우가 이에 해당한다.

여기서 생각해야할 점은, 나를 이긴 상대를 이긴 사람은
나보다 강한 사람이라는 것이다

예를 들어 1 이 2에게 지고 2가 3에게 지면 1은 3에게도 진다.

이렇게 자신보다 강한사람 몇명인지
또 약한 사람은 몇명인지 파악해야한다.

문제 풀이

1. 그래프를 그린다.
2. n ( 선수의 수 ) 만큼 DFS 를 2번 수행한다
   • n 선수 보다 약한 선수를 그래프에서 1 로 표현
   • n 선수 보다 강한 선수를 그래프에서 -1 로 표현
     → 약한사람을 처음 찾은 경우 중복을 제거하여 그 약한사람 보다 약한사람은 몇명인지
     강한 사람을 처음 찾은 경우 중복을 제거해가며 강한사람보다 더 강한사람은 몇명인지 구한다.
   • 구하고 난 후 두가지 경우의 사람들의 합이 자신을 제외한 전체 선수들의 수와 같으면 순위를 얻을 수 있다.

            HashSet<Integer> higher = new HashSet<>();
            HashSet<Integer> lower  = new HashSet<>();
            int high = DFS(higher,i,1).size();
            int low  = DFS(lower,i,-1).size();
            if(high+low == n-1){
                answer++;
            }

코드

package n_49191_240715;


import java.util.*;

// ** https://school.programmers.co.kr/learn/courses/30/lessons/49191
public class Main {

    public static void main(String[] args) {
        int n1 = 5;
        int[][] result_1 = {{4, 3},{4, 2},{3, 2},{1, 2},{2, 5}};

        Main m = new Main();
        System.out.println(m.solution(n1,result_1));;

    }

    public int[][] graph;
    public int     size;


    public int solution(int n, int[][] results) {
        graph = new int[n][n];
        size  = n;
        for(int i = 0; i<results.length; i++){
            int row = results[i][0]-1;
            int col = results[i][1]-1;
            graph[row][col] =  1;
            graph[col][row] = -1;
        }

        int answer = 0 ;

        for(int i = 0 ; i<n; i++){
            HashSet<Integer> higher = new HashSet<>();
            HashSet<Integer> lower  = new HashSet<>();
            int high = DFS(higher,i,1).size();
            int low  = DFS(lower,i,-1).size();

            if(high+low == n-1){
                answer++;
            }

        }
        return answer;
    }

    public Set<Integer> DFS(Set<Integer> set, int n, int upAndDown){
        for(int i = 0; i<size;i++){
            int currentInt = graph[n][i];
            if(currentInt == upAndDown && !set.contains(i)){
                set.add(i);
                DFS(set,i,upAndDown);
            }
        }
        return set;
    }
}

풀이 결과