[프로그래머스] 순위 (go, python)

문제

문제 설명

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

입출력 예 설명

2번 선수는 [1, 3, 4] 선수에게 패배했고 5번 선수에게 승리했기 때문에 4위입니다.
5번 선수는 4위인 2번 선수에게 패배했기 때문에 5위입니다.

---

풀이

• '모든 선수' 들에서 '모든 선수' 들의 관계를 알아야 하는 문제로 플로이드-워셜 알고리즘으로 해결한다.
• 시간복잡도가 O(N^3)이지만 선수는 최대 100이기 때문에 위 알고리즘을 사용할 수 있다.
• 한 선수의 순서를 알기 위해서는 해당 선수와 다른 n-1명의 선수와의 관계를 알아야 한다.
• [i, j]를 모르더라도 [i, k], [k, j]를 통해 [i, j] 임을 알 수 있다.
• 주어지지 않은 모든 관계에 대해서 위 조건이 성립하는 관계를 찾는다.

Go

func solution(n int, results [][]int) int {
	var grid = make([][]int, n)
	for i := 0; i < n; i++ {
		grid[i] = make([]int, n)
	}

	for _, match := range results {
		grid[match[0]-1][match[1]-1] = 1
	}

	for k := 0; k < n; k++ {
		for i := 0; i < n; i++ {
			for j := 0; j < n; j++ {
				if grid[i][j] == 0 && grid[i][k] == 1 && grid[k][j] == 1 {
					grid[i][j] = 1
				}
			}
		}
	}

	counts := make([]int, n)
	for i := 0; i < n; i++ {
		for j := i+1; j < n; j++ {
			if grid[i][j] == 1 {
                counts[i]++
                counts[j]++
			}
            if grid[j][i] == 1 {
                counts[i]++
                counts[j]++
            }
		}
	}

	var cnt int
	for _, count := range counts {
		if count == n-1 {
			cnt++
		}
	}

	return cnt
}

테스트 1 〉	통과 (0.00ms, 4.16MB)
테스트 2 〉	통과 (0.01ms, 3.92MB)
테스트 3 〉	통과 (0.01ms, 3.91MB)
테스트 4 〉	통과 (0.02ms, 3.76MB)
테스트 5 〉	통과 (0.07ms, 4.18MB)
테스트 6 〉	통과 (0.23ms, 4.19MB)
테스트 7 〉	통과 (0.84ms, 4.2MB)
테스트 8 〉	통과 (1.68ms, 4.14MB)
테스트 9 〉	통과 (2.20ms, 4.2MB)
테스트 10 〉	통과 (3.04ms, 4.16MB)

Python

def solution(n, results):
	# 선수들간의 관계 초기화
    arr = [[0] * n for _ in range(n)]
    for (a, b) in results:
        arr[a-1][b-1] = 1
       
    # [i, k], [k, j]를 통해 [i, j] 관계 확장
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if i == j:
                    continue
                
                if arr[i][j] == 0 and arr[i][k] and arr[k][j]:
                    arr[i][j] = 1
    
    # [i, j] | [j, i] 
    for i in range(n):
        for j in range(n):
            if arr[i][j] == 1:
                arr[j][i] = 1
            
            if arr[j][i] == 1:
                arr[i][j] = 1
	
    # 관계의 수가 n-1인 선수들 카운팅
    answer = 0
    for row in arr:
        if sum(row) == n - 1:
            answer += 1
    
    return answer

테스트 1 〉	통과 (0.03ms, 10.3MB)
테스트 2 〉	통과 (0.12ms, 10.3MB)
테스트 3 〉	통과 (0.15ms, 10.2MB)
테스트 4 〉	통과 (1.91ms, 10.1MB)
테스트 5 〉	통과 (3.05ms, 10.4MB)
테스트 6 〉	통과 (8.22ms, 10.1MB)
테스트 7 〉	통과 (38.14ms, 10.3MB)
테스트 8 〉	통과 (76.75ms, 10.3MB)
테스트 9 〉	통과 (132.34ms, 10.4MB)
테스트 10 〉	통과 (111.00ms, 10.8MB)