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

November 2, 2024

🔐 프로그래머스 - 순위

n명의 선수들의 경기 결과가 주어졌을 때, 순위를 확실히 정할 수 있는 선수의 수를 반환하도록

하는 문제이다. 순위를 확실히 정할 수 있으려면 n명의 선수가 있다고 가정할 때, 어떤 선수 A는

n-1 개의 경기 결과가 존재해야만 한다.

하지만, 단순히 주어지는 경기 결과만으로는 선수들간의 모든 승패 관계를 파악하기 어렵다.

문제의 예시처럼, 5명의 선수 중 2번 선수가 (1, 3, 4)번 선수에게 패하고, 5번 선수에게 승리했다는

정보로 5번 선수가 (1, 3, 4) 번에게도 패배한다는 것을 도출해야만 한다.

즉, 선수 i가 선수 k에게 이겼고, 선수 k가 선수 j에게 이겼다면, 선수 i 역시 선수 j에게

이긴 것이 된다. if (win[i][k] && win[k][j]) win[i][j] = true;

이렇게 모든 선수들에 대한 승패를 저장하는 테이블을 채우고, 한 선수에게 n-1개의

승패 데이터가 존재한다면, 순위를 매길 수 있는 것이다.