[프로그래머스/Python] 순위 - Level3

[프로그래머스/Python] 순위 - Level3

728x90

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

이 문제는 처음봤을 때 이기고 지는 관계이므로 선후관계가 있다고 생각해서 위상정렬을 사용해서 풀어야겠다고 생각했었다. 위상정렬로 풀려고보니 위상정렬을 사용하기 위한 조건을 만족하지 못했다. 다른 사람의 풀이를 보고 사용한 알고리즘만 확인했다. 플로이드 워셜 알고리즘을 사용하면 풀 수 있었다. 예전에 공부한 것을 바탕으로 문제를 풀었다.

def solution(n, results): answer = 0 graph = [[0] * (n+1) for _ in range(n+1)] # 승패여부를 저장할 그래프 # 이기면 1, 지면 -1로 그래프에 저장 for win, lose in results: graph[win][lose] = 1 graph[lose][win] = -1 # 플로이드 워셜 수행 for k in range(1, n+1): for a in range(1, n+1): for b in range(1, n+1): if a != b and graph[a][b] == 0: # 자기 자신이 아니면서 아직 승패여부를 알 수 없는 노드라면 if graph[a][k] == 1 and graph[k][b] == 1: # a가 k를 이기고 k가 b를 이기면 a가 b를 이김 graph[a][b] = 1 elif graph[a][k] == -1 and graph[k][b] == -1: # a가 k에게 지고 k가 b에게 지면 a가 b에게 짐 graph[a][b] = -1 # 순위를 매길 수 있는 선수 세기 for i in range(1, n+1): if graph[i][1:].count(0) == 1: answer += 1 return answer

1. 승패 여부를 저장할 그래프를 생성한다. (선수 번호와 인덱스를 맞추기 위해 n+1까지 생성함)

2. results 를 돌면서 이기면 1, 지면 -1 를 그래프(graph)에 저장한다.

3. 플로이드 워셜 알고리즘을 수행한다.

3-1. 자기 자신이 아니면서 아직 승패 여부를 알 수 없는 노드라면 승패 여부를 따질 수 있는지 확인한다.

3-2. a가 k를 이기고 k가 b를 이기면 a가 b를 이기므로 graph[a][b] = 1 로 만들어준다.

3-3. a가 k에게 지고 k가 b에게 지면 a가 b에게 지므로 graph[a][b] = -1 로 만들어준다.

4. 순위를 매길 수 있는 선수를 센다.

4-1. graph[i][1:] 에 0이 하나이면 자기 자신을 제외하고 모든 노드에 승패 여부를 알 수 있다는 의미이므로 anwer에 +1을 한다.

다른 사람의 풀이를 찾아보니 이 문제는 여러 가지 방법이 있는 것 같다.

① DFS (스택)

def solution(n, results): chart = [[0] * n for _ in range(n)] # 승패표 WIN, LOSE = 1, -1 for i, j in results: # 내입장 wind = 상대방 lose chart[i-1][j-1], chart[j-1][i-1] = WIN, LOSE for me in range(n): wins = [opp for opp, rst in enumerate(chart[me]) if rst == WIN] while wins: loser = wins.pop() for opp, rst in enumerate(chart[loser]): if rst == WIN and chart[me][opp] == 0: chart[me][opp], chart[opp][me] = WIN, LOSE wins.append(opp) return len(['know' for x in chart if x.count(0) == 1])

② 딕셔너리

from collections import defaultdict def solution(n, results): answer = 0 wins = defaultdict(set) loses = defaultdict(set) for a, b in results: wins[a].add(b) loses[b].add(a) for i in range(1, n+1): for loser in wins[i]: loses[loser] |= loses[i] for winner in loses[i]: wins[winner] |= wins[i] for i in range(1, n+1): if len(wins[i]) + len(loses[i]) == n - 1: answer += 1 return answer

728x90

from http://soohyun6879.tistory.com/184 by ccl(A) rewrite - 2021-08-09 12:00:36