[프로그래머스] 순위

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

풀이

모든 선수와의 승패를 알 수 있다면 순위가 결정될 것이다. 따라서 이 문제의 핵심은 한 선수에 대해서 승패 결과의 갯수가 n-1개이면 순위가 결정된다는 것이다. 따라서 모든 선수의 승패 결과를 만들어줘야하는데, 해당 문제에서는 선수의 수가 최대 100명이므로 플로이드-와샬 알고리즘으로 모든 경우를 구할 수 있다. 따라서 플로이드 와샬 알고리즘을 사용해서 모든 경우의 승패를 표시한 뒤, 갯수를 세어주면 해결할 수 있다.

코드

C++

#include <string>
#include <vector>
using namespace std;

int solution(int n, vector<vector<int>> results) {
    int answer = 0;

    vector<vector<bool>> win(n + 1, vector<bool>(n + 1, false)); // 승리 관계 표현 벡터

    // 승리한 경우 true로 표시
    for (int i = 0; i < results.size(); i++)
        win[results[i][0]][results[i][1]] = true;

    // 플로이드 와샬 알고리즘
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                // i가 k를 이기고 k가 j를 이겼으면 i가 j를 이긴 것으로 표시
                if (win[i][k] && win[k][j]) 
                    win[i][j] = true;
    }

    for (int i = 1; i <= n; i++) {
        int cnt = 0;
        for (int j = 1; j <= n; j++)
            // 이기거나 진 결과 카운트
            if (win[i][j] || win[j][i]) cnt++;
        // 자기 자신과는 싸울 수 없기 때문에 n-1의 결과가 나오면 순위가 결정됨
        if (cnt == n - 1) answer++;
    }

    return answer;
}

Java

class Solution {
    boolean[][] win;

    public int solution(int n, int[][] results) {
        int answer = 0;
        win = new boolean[n + 1][n + 1]; // 승리 관계 표현 배열

        // 승리한 경우 true로 표시
        for (int[] result : results)
            win[result[0]][result[1]] = true;

        // 플로이드 와샬 알고리즘
        for (int k = 1; k <= n; k++)
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= n; j++)
                    // i가 k를 이기고 k가 j를 이겼으면 i가 j를 이긴 것으로 표시
                    if (win[i][k]  && win[k][j])
                        win[i][j] = true;


        for (int i = 1; i <= n; i++) {
            int count = 0;
            for (int j = 1; j <= n; j++) {
                // 이기거나 진 결과 카운트
                if (win[i][j] || win[j][i]) count++;
            }
            // 자기 자신과는 싸울 수 없기 때문에 n-1의 결과가 나오면 순위가 결정됨
            if (count == n - 1) answer++;
        }
        return answer;
    }
}