[ 프로그래머스 / Programmers Level 3 ] 순위

https://programmers.co.kr/learn/courses/30/lessons/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 선수를 이겼다는 의미입니다.
• 모든 경기 결과에는 모순이 없습니다.

 

 

풀이

---

https://hyeyun.tistory.com/entry/Algorithm-플로이드-와샬-Floyd-Warshall-알고리즘

[ Algorithm ] 플로이드 와샬 ( Floyd-Warshall) 알고리즘

 

플로이드 와샬 알고리즘으로 풀었따!🙌

처음에 문제도 이해안가고 해서 결국 질문들을 읽고 해결했ㄸ...ㅏ...ㅏ

 

1. floyd[ i ][ j ] 에 i 선수가 j 선수에게 이겼으면 1, 졌으면 0을 저장
2. 거쳐가는 선수 k 를 두고, i 선수가 k 선수에게 이기고, k 선수가 j 선수에게 이겼다면‼️ 👉 i 선수는 j 선수보다 순위가 높을 수 밖에 없기 때문에 floyd[ i ][ j ] = 1로 업데이트
3. 반대로, i 선수가 k 선수에게 지고, k 선수가 j 선수에게 졌다면 ‼️  👉 i 선수는 j 선수보다 순위가 낮기 때문에 floyd[ i ][ j ] = 0으로 업데이트
4. 각 행을 돌면서, i != j 이고, 모든 값이 처음 초기화한 -1 이 아니라면 answer++ 해주었따 💁‍♀️

어렵진않은데,,  이 알고리즘 생각하기가 진쫘 쉽지않은듯....🤦‍♀️

코드

---

public class 순위 {

    public static int solution(int n, int[][] results) {
        // Floyd Warshall 알고리즘 이용 풀이

        int answer = 0;

        int[][] floyd = new int[n + 1][n + 1];

        // -1 로 초기화
        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < n + 1; j++) {
                floyd[i][j] = -1;
            }
        }

        // 이긴선수는 1 , 진 선수는 0
        for (int i = 0; i < results.length; i++) {
            int win = results[i][0];
            int lose = results[i][1];

            floyd[win][lose] = 1;
            floyd[lose][win] = 0;
        }

        // k = 거쳐가는 선수
        for (int k = 1; k < n + 1; k++) {
            // i = 춣발하는 선수
            for (int i = 1; i < n + 1; i++) {
                // 본인은 패스
                if(k == i)
                    continue;
                for (int j = 1; j < n + 1; j++) {
                    if (i == j || k == j)
                        continue;

                    // i선수가 k선수에게 졌는데, k선수가 j선수에게 지면 -> i선수는 j선수에게 짐
                    if(floyd[i][k] == 0 && floyd[k][j] == 0)
                        floyd[i][j] = 0;
                    // i선수가 k선수에게 이겼는데, k선수가 j선수에게 이기면 -> i선수는 j선수에게 이김
                    else if(floyd[i][k] == 1  && floyd[k][j] == 1)
                        floyd[i][j] = 1;
                    
                }

            }
        }

        for (int i = 1; i < n + 1; i++) {
            boolean flag = true;
            for (int j = 1; j < n + 1; j++) {
                if (i == j)
                    continue;
                if (floyd[i][j] == -1) {
                    flag = false;
                    break;
                }
            }
            if (flag)
                answer++;
        }

        return answer;
    }

    public static void main(String[] args) {
        int[][] results = { { 4, 3 }, { 4, 2 }, { 3, 2 }, { 1, 2 }, { 2, 5 } };
        System.out.println(solution(5, results));
    }
}