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

 

코딩테스트 연습 - 순위 | 프로그래머스

5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2

programmers.co.kr

처음에는 그래프로 분류되어 있길래 위상정렬 문제인가 싶어서 한참 고민한 문제.

'플로이드 마샬 알고리즘'이라고 하는데... 처음 들어본다.

 

이 문제의 핵심은 '선수 A'가 있을 때, A를 이긴 사람과 A에게 진 사람의 수를 합치면 n-1이 되도록 만드는 것.

그리고 "A에게 진 사람은 A를 이긴 사람에게 반드시 진다' 와 'A를 이긴 사람은 A에게 진 사람을 반드시 이긴다'는 조건.

 

위 문제의 예시라면,

2번 선수가 5번 선수를 이겼고 1,3,4번 선수에게 졌다는 것은

 

'2번 선수에게 진' 5번 선수는 '2번 선수를 이긴' 1, 3, 4번에게 반드시 진다.

'2번 선수를 이긴' 1, 3, 4번 선수는 '2번 선수에게 진' 5번에게 반드시 이긴다.

 

라는 의미다.

 

명제부터가 꽤나 헷갈리고, 코드 짤 때 변수 이름때문에 한 번 더 헷갈리는 유형의 문제..

 

 

+ Recent posts