[프로그래머스] 순위 C++

[프로그래머스] 순위 C++

문제 링크 : 프로그래머스 순위

코딩테스트 연습 - 순위

 

문제 설명

n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다.

선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선순의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 선수의 수는 1명 이상 100명 이하입니다.
• 경기 결과는 1개 이상 4,500개 이하입니다.
• result 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미입니다.
• 모든 경기 결과에는 모순이 없습니다.

 

입출력 예

n	results	return
5	[[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]]	2

입출력 예 설명

2번 선수는 [1, 3, 4] 선수에게 패배했고 5번 선수에게 승리했기 때문에 4위입니다.
5번 선수는 4위인 2번 선수에게 패배했기 때문에 5위입니다.

 

---

코드 (풀다가 포기한 코드)

#include <iostream>
#include <string>
#include <vector>

using namespace std;

// 선수의 수, 경기 결과 = 2차원 배열
int solution(int n, vector<vector<int>> results) {
    int answer = 0;

    // winList[i][0] ~ winList[i][n] i번 선수가 이긴 사람들
    vector<vector<int>> winList(n+1);
    // lostList[i][0] ~ loseList[i][n] i번 선수가 진 사람들
    vector<vector<int>> loseList(n+1);
    // 점수 체크
    vector<int> score(n+1, 0);

    for(int i = 0; i < results.size(); i++) {
        int winner = results[i][0];
        int loser = results[i][1];

        winList[winner].push_back(loser);
        loseList[loser].push_back(winner);
    }

    for(int winner = 1; winner <= n; winner++) {
        score[winner] += (int) winList[winner].size();
        score[winner] -= (int) loseList[winner].size();
    }

    for(int i = 1; i <= n; i++) {
        cout << i << " : " << score[i] << endl;
    }


    return answer;
}

 

풀이 과정 (정답)

전형적인 플로이드 와샬 알고리즘을 이용하는 문제다. 나도 사실은 플로이드 와샬을 잘 몰랐는데 한 시간 안으로 문제가 안풀리길래 찾아보고 나서 알았다 데헷. 근데 마지막에 둘중에 승패가 확실한 경우가 왜 winCount==인원수-1 인지를 모르겠다 이해가 안간다. 아시는 분 댓글좀... 지져스 세이브 미...

 

9월 8일 21시 수정 사항

• winCount == 인원수 - 1 이 승패가 왜 확실한가? 그것은 바로, 당사자 빼고 모든 사람들의 전적을 알 수 있기 때문으로 해석할 수 있겠다. 당사자를 뺀 카운트 수가 인원수 - 1 이니, 이때야 말로 비로소 모든 승패를 알 수 있는 경우인것이다.
• 해당 내용 알려준 찬영이 형에게 무한 땡스 브라덜!

 

코드

#include <iostream>
#include <string>
#include <vector>

using namespace std;

// 선수의 수, 경기 결과 = 2차원 배열
int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    vector<vector<bool>> graph(n+1, vector<bool>(n+1, false));

    // 승리한 경우 추가
    for(auto r : results) {
        int winner = r[0];
        int loser = r[1];
        graph[winner][loser] = true;
    }

    // 플로이드 와샬 적용
    for(int b = 1; b <= n; b++) {
        for(int a = 1; a <= n; a++) {
            for(int c = 1; c <= n; c++) {
                // a가 b를 이겼고 b가 c를 이겼으면, a가 c를 이겼다고 표시
                if(graph[a][b] && graph[b][c])
                    graph[a][c] = true;
            }
        }
    }

    for(int i = 1; i <= n; i++) {
        int winCount = 0;
        for(int j = 1; j <= n; j++) {
            if(i == j) continue;
            // a가 b를 이겼거나 b가 a를 이긴 경우
            if(graph[i][j] || graph[j][i])
                winCount++;
        }
        // 둘중에 승패가 확실한 경우
        if (winCount == n-1)
            answer++;
    }

    return answer;
}

---

Reference

• https://mungto.tistory.com/58