[코딩테스트] Java 순위

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

잃어버린 결과표에서 순위를 알 수 있는 선수의 수를 구하는 문제였습니다.
순위를 안다는 것은 누군가에게 지고 이겼는지에 대한 모든 결과를 알고 있으면 되므로 wins 배열과 loses 배열을 통해 확인합니다.

소스코드

import java.util.*;

class Solution {
    List<List<Integer>> wins = new ArrayList<>();
    List<List<Integer>> loses = new ArrayList<>();
    
    public int solution(int n, int[][] results) {
        int answer = 0;
        
        for(int i = 0; i <= n; i++) {
            wins.add(new ArrayList<>());
            loses.add(new ArrayList<>());
        }
        
        for(int[] result: results) {
            int win = result[0];
            int lose = result[1];
            wins.get(win).add(lose);
            loses.get(lose).add(win);
        }
        
        for(int i = 1; i <= n; i++) {
            boolean[] visited = new boolean[n + 1];
            Queue<Integer> q = new LinkedList<>();
            
            visited[i] = true;
            q.add(i);
            while(!q.isEmpty()) {
                int win = q.poll();
                for(int lose: wins.get(win)) {
                    if (visited[lose]) continue;
                    visited[lose] = true;
                    q.add(lose);
                }
            }
            
            q.add(i);
            while(!q.isEmpty()) {
                int lose = q.poll();
                for(int win: loses.get(lose)) {
                    if (visited[win]) continue;
                    visited[win] = true;
                    q.add(win);
                }
            }
            
            boolean flag = true;
            for(int j = 1; j <= n; j++) {
                if(!visited[j]) {
                    flag = false;
                }
            }
            if (flag) {
                answer++;
            }
        }
        
        return answer;
    }
}

코드 설명

• 변수 설명
  • List<List<Integer>> wins = new ArrayList<>();
    List<List<Integer>> loses = new ArrayList<>();
    src가 이긴 desc가 진 배열이 wins 배열, src가 진 desc가 이긴 배열이 loses 배열입니다.

for(int i = 0; i <= n; i++) {
    wins.add(new ArrayList<>());
    loses.add(new ArrayList<>());
}

for(int[] result: results) {
    int win = result[0];
    int lose = result[1];
    wins.get(win).add(lose);
    loses.get(lose).add(win);
}

• wins 배열과 loses 배열을 초기화합니다.

for(int i = 1; i <= n; i++) {
    boolean[] visited = new boolean[n + 1];
    Queue<Integer> q = new LinkedList<>();

    visited[i] = true;
    q.add(i);
    while(!q.isEmpty()) {
        int win = q.poll();
        for(int lose: wins.get(win)) {
            if (visited[lose]) continue;
            visited[lose] = true;
            q.add(lose);
        }
    }

    q.add(i);
    while(!q.isEmpty()) {
        int lose = q.poll();
        for(int win: loses.get(lose)) {
            if (visited[win]) continue;
            visited[win] = true;
            q.add(win);
        }
    }

• 첫번째 while문을 통해 i가 이긴 선수들과 이긴 선수들의 결과표를 통해 인덱스를 방문합니다.
• 두번째 while문을 통해 i가 진 선수들과 진 선수들의 결과표를 통해 인덱스를 방문합니다.

boolean flag = true;
    for(int j = 1; j <= n; j++) {
        if(!visited[j]) {
            flag = false;
        }
    }
    if (flag) {
        answer++;
    }
}

return answer;

• 모든 배열을 방문하였다면 순위를 알 수 있는 것이므로 answer를 증가하고 반복문 종료시 answer를 반환합니다.
•