💻코딩테스트 문제풀이18

Chapter11. 자주 등장하는 자료 구조

[문제46] 순위 - Level3

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

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

[제한사항]

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

[코드작성]

1. 승/패 정보를 담을 딕셔너리를 정의

from collections import defaultdict

def solution(n, results):
	answer = 0
    win, lose = defaultdict(set), defaultdict(set)

2. 주어진 결과에서 승/패 정보를 모두 기록

for winner, loser in results:
	win[loser].add(winner)
    lose[winner].add(loser)

3. 특수 조건을 반영

for i in range(1, n+1)
	for winner in win[i]:
    	lose[winner].update(lose[i])
    for loser in lose[i]:
    	win[loser].update(winner[i])

4. 각 선수가 승/패 경기를 합친 결과가 총 n - 1개인지 확인

for i in range(1, n+1)
	if len(win[i]) + len(lose[i]) == n - 1:
    	answer += 1

[전체코드]

from collections import defaultdict

def solution(n, results):
	answer = 0
    win, lose = defaultdict(set), defaultdict(set)
    
    for winner, loser in results:
		win[loser].add(winner)
    	lose[winner].add(loser)
        
    for i in range(1, n+1)
      for winner in win[i]:
          lose[winner].update(lose[i])
      for loser in lose[i]:
          win[loser].update(winner[i])
          
    for i in range(1, n+1)
      if len(win[i]) + len(lose[i]) == n - 1:
          answer += 1
          
	return answer

[코드작성2]

1. 승/패 정보를 담을 그래프를 생성

def solution(n, results):
	total = [[0 for i in range(n)] for j in range(n)]

	for i in rnage(n):
    	total[i][i] = 'SELF'

2. 주어진 결과에서 승/패 정보를 기록

for result in results:
	total[result[0] - 1][result[1] - 1] = 'WINS'
    total[result[1] - 1][result[0] - 1] = 'LOSE'

3. 플로이드-워셜 알고리즘 사용

for k in range(n):
	for i in range(n):
    	for j in range(n):
        	if total[i][k] == 'WINS' and total[k][j] == 'WINS': total[i][j] = 'WINS'
            if total[k][j] == 'LOSE' and total[k][j] == 'LOSE' : total[i][j] = 'LOSE'

4. 정해지지 않은 값이 있는지 확인

answer = 0
	
for i in total:
	if 0 not in i: answer += 1

[전체코드2]

def solution(n, results):
	total = [['????' for i in range(n)] for j in range(n)]

	for i in rnage(n):
    	total[i][i] = 'SELF'
        
    for result in results:
        total[result[0] - 1][result[1] - 1] = 'WINS'
        total[result[1] - 1][result[0] - 1] = 'LOSE'
        
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if total[i][k] == 'WINS' and total[k][j] == 'WINS': total[i][j] = 'WINS'
                if total[k][j] == 'LOSE' and total[k][j] == 'LOSE' : total[i][j] = 'LOSE'
                
    answer = 0

    for i in total:
        if '????' not in 1:
        	answer += 1
            
    return answer