[Algorithm] Tournament Winner

  오늘 풀어볼 문제 상황은 Tournament Winner 이다. Problem solving 실력을 겨루는 Tournament Winner 는 아래의 규칙을 따른다.

• 각각의 team 은 서로 다른 언어(C#, Python ...)를 사용한다.
• 경기 방식은 round-robin 리그제이며 각 경기 당 home team, away team 이 지정된다.
• 대진표는 competitions 2차원 배열에 제시되며 경기 결과는 results 배열로 주어진다.
  competitions = [
      ["HTML", "C#"],
      ["C#", "Python"],
      ["Python", "HTML"],
  ]
  results = [0, 0, 1]
  위와 같이 주어졌을 때, 각각의 대진표의 앞의 팀은 home, 뒤에 팀은 away 이다. 그리고 results 가 0 이면 away 가 이긴 것이며 1 이면 home 팀이 승리한 것이다.
• 경기에 승리한 팀은 3 point 를 얻게 되며, 최종적으로 가장 많은 점수를 가지고 있는 team 이 우승팀이고, 우승팀이 여러개 나오는 경우는 제외한다.

  각각의 팀을 hash table 에 <teamname, score> 의 형태로 저장하면 문제를 쉽게 해결할 수 있다. competitions 배열에서 teamname 을 뽑아내서 hash_table 에 {teamname, 0} 의 형태로 insert 해준다. 그리고 경기 개수만큼 loop 를 돌며 results 의 원소에 따라서 home team, away team 에 3점을 부여한다. 이후에 hash_table 을 순회하며 score 가 가장 높은 teamname 을 반환하면 된다. 

  경기 개수를 N, 팀 개수를 K 라고 했을 때 시간 복잡도는 O(N) 이고 공간 복잡도는 O(K) 이다.

#include <vector>
using namespace std;

// Time  : O(N) (N is # of competitions)
// Space : O(k) (k is # of teams) ~ hash map

string tournamentWinner(vector<vector<string>> competitions,
    vector<int> results) {
    // Write your code here.
    unordered_map<string, int> m;
    for (vector<string> ele : competitions) {
        m.insert({ ele[0], 0 });
        m.insert({ ele[1], 0 });
    }
    for (int i = 0; i < competitions.size(); i++) {
        if (results[i] == 1) {
            // home team win
            m[competitions[i][0]] += 3;
        }
        else {
            // away team win
            m[competitions[i][1]] += 3;
        }
    }
    string winner = ""; int max_pt = -1;
    for (auto ele : m) {
        if (ele.second > max_pt) {
            max_pt = ele.second;
            winner = ele.first;
        }
    }
    return winner;
}

https://github.com/versatile0010/AlgoExpert

GitHub - versatile0010/AlgoExpert: Solutions to AlgoExpert Problems.