99클럽 코테 스터디 4일차 TIL : Graph, 프로그래머스, 순위

문제

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

프로그래머스

 

통과 여부

Fail

 

나의 접근법 (해결 못 함)

• '방향'과 '순위' 에 꽂혀 위상 정렬 문제라고 생각하고 문제 풀기 시작
• [[], [이긴 상대1, 2,...], [], ...] 처럼 각 선수 별로 이긴 상대를 List에 담은 2차원 List 로 초기화
• 나 > 상대일 때, 상대 > 타 선수 이면, 나 > 타 선수 이므로  위 2차원 List 를 순회하면서 각 선수 별로 이긴 상대를 Update 함. 
• 각 선수 별로 승리 횟수를 진입 차수로 두고 진입차수가 0 인 선수부터 answer 에 삽입.
• 위상 정렬 도중 더 이상 answer 에 삽입할 수 있는 값이 없으면 answer에 삽입된 값의 수를 Return.

 

그러나 결국 나는 문제를 끝까지 풀지 못했고,,, 정규 스터디 시간을 통해 다른 참가자들은 위상 정렬이 아닌 Floyd-Warshall 또는 BFS 로 문제를 풀이했다는 사실을 알았다. Algorithm 이론이 부족하여 발생했던 경우... 재도전 다짐!