[Java][Programmers]49191_순위

문제 설명 n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다. 선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요. 제한사항 선수의 수는 1명 이상 100명 이하입니다. 경기 결과는 1개 이상 4,500개 이하입니다. results 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미입니다. 모든 경기 결과에는 모순이 없습니다.

 

문제에서 요구하는 "정확하게 순위를 매길 수 있는 선수" 의 조건은 무엇일까?

바로, 다른 모든 선수와의 경기에서 누가 지고, 누가 이길지 알 수 있는 것이다.

직접 경기를 하지 않은 선수더라도 다른 선수와의 경기결과를 분석하여 본인과의 경기 결과를 예측할 수 있어야하고,

본인과의 경기 결과를  추측할 수 없는 선수가 존재하지 않아야한다.

 

풀이는 다음과 같은 로직으로 수행하였다.

 

  * 준비: array에 각각 1~n번 선수에게 패배한 선수 arrayList, 승리한 선수 arrayList를 저장. 

1. x번 선수 선택
2. x번 선수보다 낮은 순위에 존재할 선수들 탐색 ( 재귀함수를 통해, Set에 추가)
   x에게 진 모든 선수(a,b,c라고 가정) -> a,b,c선수의 경기에서 진 선수 -> .... 
3. x번 선수보다 높은 순위에 존재할 선수들 탐색 ( 재귀함수를 통해, Set에 추가)
   x에게 이긴 모든 선수(a,b,c라고 가정) -> a,b,c선수의 경기에서 이긴 선수 -> .... 
4. set에 추가된 선수들이 모든 선수의 수 N과 같으면 결과값 COUNT
5. 1~N번 선수까지 위 로직을 반복하여 결과값을 구한다.

 

설명보다는 소스코드를 보자.

class Solution {
    
    public Set<Integer> set = new HashSet<>();
    public ArrayList<Integer>[][] list;
    
    public int solution(int n, int[][] results) {
        
        list = new ArrayList[n+1][2]; // 0 진 선수들, 1 이긴 선수들
        for(int i=0; i<n+1; i++) {
            list[i][0] = new ArrayList<>();
            list[i][1] = new ArrayList<>();
        }
        
        for(int i=0; i<results.length; i++) { // 진 선수, 이긴 선수를 lsit에 추가
            list[results[i][0]][0].add(results[i][1]); //results[i][0] 승자, results[i][1] 패자
            list[results[i][1]][1].add(results[i][0]);
        }
        
        int answer = 0;
        for(int i=1; i<n+1; i++) {
            set.add(i);
            findWinner(i);  // i에게 이긴 선수 찾기
            findLoser(i); // i에게 진 선수 찾기
            if(set.size() == n)  // set에 승부를 파악한 선수의 수가 전체인원과 같으면 순위를 매길 수 있음
                answer ++;
            set.clear();
        }
        
        return answer;
    }
    
    public void findWinner(int idx) {
        for(int i=0; i<list[idx][1].size(); i++) {
            int winner = list[idx][1].get(i);
            if(!set.contains(winner)) {
                set.add(winner);
                findWinner(winner);
            }
        }
        set.add(idx);
    }
               
    public void findLoser(int idx) {
        for(int i=0; i<list[idx][0].size(); i++) {
            int loser = list[idx][0].get(i);
            if(!set.contains(loser)) {
                set.add(loser);
                findLoser(loser);
            }
        }
        set.add(idx);
    }
}

 

---

programmers.co.kr/learn/courses/30/lessons/49191#

코딩테스트 연습 - 순위