[programmers] 순위 (level 3)

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

프로그래머스

---

문제

n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다.

선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요.

 

제한 사항

• 선수의 수는 1명 이상 100명 이하입니다.
• 경기 결과는 1개 이상 4,500개 이하입니다.
• results 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미입니다.
• 모든 경기 결과에는 모순이 없습니다.

 

입출력 예

n	results	return
5	[[4,3], [4,2], [3,2], [1,2], [2,5]]	2

---

접근법

a > b : a가 b를 이겼다

1. (n+1)x(n+1) 2차원 배열 score_board를 -1로 초기화해준다.

2. a > b이면 score_board[a][b]에 1, score_board[b][a]에 0을 넣는다.

3. 플로이드 워셜을 이용해 score_board를 채워준다. (score_board는 좌하 대각선을 기준으로 대칭이므로, 절반만 순회하기 위해 범위 값을 줄여줬다 => 아래 코드에서 person1, person2)

4. 승부가 결정나지 않은 경우 (score_board 값이 -1인 경우) 중, score_board[person1][mid_person] == score_board[mid_person][score_board]이고 (person1 > mid_person > person2 또는 person1 < mid_person < person2) 승부가 결정되었을 경우 (두 값이 모두 -1이 아닌 경우) 두 값을 갱신

5. 행 인덱스와 열 인덱스가 같지 않을 경우에, -1이 존재하면 순위가 결정되지 못했다는 의미이므로, -1이 존재하지 않는 행의 개수를 세 줌

 

풀이

def solution(n, results):
    answer = 0
    score_board = [[-1] * (n+1) for _ in range(n+1)]
    for winner, loser in results:
        score_board[winner][loser] = 1
        score_board[loser][winner] = 0
    for mid_person in range(1, n+1):
        for person1 in range(1, n):
            if person1 != mid_person:
                for person2 in range(person1+1, n+1):
                    if score_board[person1][person2] == -1:
                        one_to_mid = score_board[person1][mid_person]
                        mid_to_two = score_board[mid_person][person2]
                        if one_to_mid == mid_to_two != -1:
                            score_board[person1][person2] = one_to_mid
                            score_board[person2][person1] = 1 - one_to_mid
    for i in range(1, n+1):
        for j in range(1, n+1):
            if i != j:
                if score_board[i][j] == -1:
                    break
        else:
            answer += 1
    return answer
    
정확성  테스트
테스트 1 〉	통과 (0.03ms, 10.3MB)
테스트 2 〉	통과 (0.07ms, 10.2MB)
테스트 3 〉	통과 (0.07ms, 10.2MB)
테스트 4 〉	통과 (1.06ms, 10.1MB)
테스트 5 〉	통과 (1.66ms, 10.2MB)
테스트 6 〉	통과 (2.44ms, 10.2MB)
테스트 7 〉	통과 (11.78ms, 10.3MB)
테스트 8 〉	통과 (22.87ms, 10.6MB)
테스트 9 〉	통과 (28.44ms, 10.7MB)
테스트 10 〉	통과 (29.05ms, 10.6MB)