Algorithm) Programmers Level3 순위 c++

https://school.programmers.co.kr/learn/courses/30/lessons/49191

프로그래머스

그래프 문제였습니다. 아이디어 떠올리기도 어렵지 않고 구현도 어렵지 않은 무난한 문제였습니다

 

풀이 방법을 보면

 

 

우선 이겼을때와 졌을때 상황을 나눴습니다

이긴 경우 ->  A가 B를 이기고 B가 C를 이겼다면 A는 C를 이깁니다.

진 경우 -> B가 A를 이기고 C가 B를 이기면 C가 A를 이깁니다

위 로직을 구현한 것이 whenWin, whenLose 함수입니다.

 

구현한 함수들을 모든 선수들에 대해 진행한다면 답을 도출해낼 수 있습니다

 

+++

unordered_set을 사용한 이유는 처음 구현할땐 set을 썼었지만 생각해보니 unordered_set을 사용하면 더 빠르게 만들 수 있겠다는 생각이 들어 unordered_set으로 바꿨습니다! 

 

그리고 set에 넣기전 해당 값이 존재하는지 확인하는 로직을 넣어서 중복 계산을 배제하도록 했습니다! 이 부분을 빼면 시간초과가 나더군요

 

#include <string>
#include <vector>
#include <unordered_set>

using namespace std;

vector<vector<int>> win(101);
vector<vector<int>> lose(101);

void whenWin(int person, unordered_set<int> &s) {
    for(int i=0; i<win[person].size(); i++) {
        if(s.find(win[person][i]) == s.end()) {
            s.insert(win[person][i]);
            whenWin(win[person][i], s);
        }
    }
}

void whenLose(int person, unordered_set<int> &s) {
    for(int i=0; i<lose[person].size(); i++) {
        if(s.find(lose[person][i]) == s.end()) {
            s.insert(lose[person][i]);
            whenLose(lose[person][i], s);
        }
    }
}


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

    for(int i=0; i<results.size(); i++) {
        win[results[i][0]].push_back(results[i][1]);
        lose[results[i][1]].push_back(results[i][0]);
    }

    for(int i=1; i<=n; i++) {
        unordered_set<int> s;
        for(int j=0; j<win[i].size(); j++) {
            if(s.find(win[i][j]) == s.end()) {
                s.insert(win[i][j]);
                whenWin(win[i][j], s);
            }
        }

        for(int j=0; j<lose[i].size(); j++) {
            if(s.find(lose[i][j]) == s.end()) {
                s.insert(lose[i][j]);
                whenLose(lose[i][j], s);
            }
        }

        if(s.size() == n-1) {
            answer++;
        }
    }

    return answer;
}