알고리즘) 프로그래머스 Graph, 순위

프로그래머스 고득점 Kit - Graph

순위

 

풀이

(2020.04.27)

문제의 조건에서 경기 결과에 모순이 없으며,  A>B, B>C 이면 항상 A>B>C의 순서가 매겨진다고 되어있다. 따라서, 경기 결과가 유실되어도 특정 선수(A)가 이긴 상대들은 A를 이긴 상대들이 이길 수 있다는 뜻이다. 경기 결과 입력 후, 서로 상관관계에 따라 입력을 해주고 랭킹을 부여할 수 있는 선수들을 찾아 return했다.

 

1. 전체 경기 결과를 이긴 상대 리스트, 진 상대 리스트에 담아준다. (선수 Index에 맞춰서)

2. 서로 경기 결과에 대해 이기고 진 상대들을 업데이트 해준다.

3. 경기 결과가 모두 있는 선수들은 Rank를 부여할 수 있으므로, 전체 경기 결과가 있는 선수들의 수를 return해준다.

 

(2020.06.04)

리스트를 쓰지 않고, 배열을 통해 답을 구해주었다.

처음 풀었을 때는 특정 선수가 이긴 선수들 List와 진 선수들 List를 만들어주어 확인했는데, 배열에 그냥 이기고 진 표시를 해주었다.

이긴 경우에는 1로, 진 경우에는 -1로 값을 저장해주었다.

경기 기록이 저장된 이후에는, 반복문을 통해 탐색하면서 두 가지 조건에 따라 값을 조정해주었다.

 

1. 특정 선수가 다른 선수를 이긴경우

2. 특정 선수가 다른 선수에게 진 경우

 

1 번의 경우에는 내가 이긴 상대면, 상대가 이긴 선수들을 특정 선수가 이길 수 있다고 저장해주었다.

2 번의 경우에는 내가 진 상대한테, 내가 이긴 선수들을 다 이길 수 있다고 저장해주었다.

동시에 1번과 2번에서 지는 선수의 기록도 진다고 저장해주면서 경기 기록을 완성하였다.

 

완성된 경기 기록을 돌면서 count를 통해, 몇 명이 랭크를 확정지을 수 있는지 세주었다.

 

코드 1

 

import java.util.LinkedList;

public class KitGraphRank {
    private static int solution(int n, int[][] results) {
        LinkedList<Integer>[] winnerList = inItLinkedList(n);     //i가 이긴 선수들 List
        LinkedList<Integer>[] loserList = inItLinkedList(n);      //i가 진 선수들 List

        for(int[] game : results) {
            winnerList[game[0]].offer(game[1]);  // 선수가 이긴것만 저장
            loserList[game[1]].offer(game[0]); // 선수가 진것만 저장
        }

        for(int i=1; i<=n; i++) {
            winnerList = addMatches(winnerList, loserList, i, n);   // i 선수가 이기는 상대 선수 추가
            loserList = addMatches(loserList, winnerList, i, n);    // i 선수가 지는 상대 선수 추가
        }

        return getFixCount(winnerList, loserList, n);       // Rank 를 정할 수 있는 선수 수 return
    }

    private static int getFixCount(LinkedList<Integer>[] winnerList, LinkedList<Integer>[] loserList, int n) {
        int cnt=0;
        for(int i=1; i<=n; i++) {
            if(isAllMatches(winnerList[i], loserList[i], n)) { // 경기기록이 다 있으면
                cnt++;
            }
        }
        return cnt;
    }

    private static boolean isAllMatches(LinkedList<Integer> winList, LinkedList<Integer> loseList, int n) { // 모든 경기기록 체크
        return winList.size() + loseList.size() == n-1 ? true : false;
    }

    private static LinkedList<Integer>[] inItLinkedList(int n) {    // InIt
        LinkedList<Integer>[] result = new LinkedList[n+1];
        for(int i=1; i<=n; i++) {
            result[i] = new LinkedList<>();
        }
        return result;
    }

    // 선수의 상관 관계를 업데이트 시켜줄 메소드
    private static LinkedList<Integer>[] addMatches(LinkedList<Integer>[] match1, LinkedList<Integer>[] match2, int player, int n) {
        //match1,match2가 서로 winList or loseList가 될 것임
        // match1이 WinnerList, match2가 loserList => i 선수가 이긴 선수들에게 진 선수들을 i선수가 이기는 선수들에 추가
        // 반대의 경우 => i선수가 진 선수들에게 이긴 선수들을 i 선수가 지는 선수들에 추가
        for(int origin : match2[player]) {    // match2에 담긴 player가 치룬 경기 정보를 받아와서
            for (int target : match1[player]) {  // match1에 담긴 player가 경기한 선수들
                if (!match1[origin].contains(target)) {  // 중복 체크
                    match1[origin].offer(target);        // match2에서 겨룬 선수에대해 match1에 저장
                }
            }
        }
        return match1;
    }

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

        System.out.println(solution(n, result));
    }
}

 

코드 2

 

class Solution {
    public int solution(int n, int[][] results) {
        int answer = 0;
        int[][] matches = new int[n+1][n+1];
        for(int[] match : results) {
            matches[match[0]][match[1]] = 1; // 이김
            matches[match[1]][match[0]] = -1; // 짐
        }
        
        // match 저장
        for(int player=1; player<=n; player++) {
            for(int enemy =1; enemy<=n; enemy++) {
                if(matches[player][enemy] ==1) {    // 내가 이긴 애들
                    for(int i=1; i<=n; i++) {   
                        if(matches[enemy][i] == 1) {    // 상대가 이긴 애들
                            matches[player][i] =1; // 나도 이김
                            matches[i][player] = -1;
                        }
                    }
                } else if(matches[player][enemy] ==-1) {    // 내가 진 애들
                    for(int i=1; i<=n; i++) {  
                        if(matches[player][i] ==1) { // 내가 이긴애들 다 이겨
                            matches[enemy][i] =1;
                            matches[i][enemy] =-1;
                        }
                    }
                }
            }
        }
        
        // count
        for(int y=1; y<=n; y++) {
            int cnt =0;
            for(int x=1; x<=n; x++) {
                if(matches[y][x] !=0) {
                    cnt++;
                }
            }
            if(cnt == n-1) {
                answer++;
            }
        }
        
        return answer;
    }
}