220324 - 순위
◾ 순위 : 프로그래머스 LEVEL 3
문제
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 |
◾ 풀이
1. 해설
- 선수와 경기 결과의 수가 작으므로 전체를 탐색하며 결과를 찾는다.
- 먼저, 경기 결과에 따라 승, 패에 대한 결과를 추가한다.
- 추가된 경기 결과에 따라 다른 선수의 결과를 추가한다.
- a 선수의 승리 결과 : b, a 선수의 패배 결과 : c
- b에 속한 선수들은 c에 속한 선수들에게 패배한다.
- c에 속한 선수들은 b에 속한 선수들에게 승리한다.
- set() 자료형을 통해 각 결과에 대해 반복없이 추가한다. - 합집합
2. 프로그램
문제 1
◾ 순위 : 프로그래머스 LEVEL 3
문제
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 |
◾ 풀이
1. 해설
- 선수와 경기 결과의 수가 작으므로 전체를 탐색하며 결과를 찾는다.
- 먼저, 경기 결과에 따라 승, 패에 대한 결과를 추가한다.
- 추가된 경기 결과에 따라 다른 선수의 결과를 추가한다.
- a 선수의 승리 결과 : b, a 선수의 패배 결과 : c
- b에 속한 선수들은 c에 속한 선수들에게 패배한다.
- c에 속한 선수들은 b에 속한 선수들에게 승리한다.
- set() 자료형을 통해 각 결과에 대해 반복없이 추가한다. - 합집합
2. 프로그램
- 플로이드 와샬?(https://westmino.tistory.com/20)
코드
def solution(n, results):
answer = 0
arr = [[0] * (n+1) for i in range(n+1)]
for a, b in results:
arr[a][b] = 1
arr[b][a] = -1
for k in range(1, n+1):
for i in range(1, n+1):
for j in range(1, n+1):
if i == j or arr[i][j] in [1,-1]:
continue
if arr[i][k] == arr[k][j] == 1:
arr[i][j] = 1
arr[j][i] = arr[k][i] = arr[j][k] = -1
for row in arr:
if row.count(0) == 2:
answer += 1
return answer
- wins, loses 초기화
- 경기 결과 추가
- 승리한 선수 wins
- 패배한 선수 loses
- 각 선수의 승리, 패배 결과를 통해 다른 선수 결과를 추측한다.
- a가 승리한 선수들은 a가 패배한 선수들에게 패배한다.
- a가 패배한 선수들은 a가 승리한 선수들에게 승리한다.
- 각 선수의 순위를 매길 수 있는지 검사한다.
- wins, loses의 원소의 수 합이 n-1인 경우 순위를 특정할 수 있다.
# 코드
def solution(n, results):
answer = 0
wins = {i : set() for i in range(1, n+1)}
loses = {i : set() for i in range(1, n+1)}
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[loser].union(loses[i])
for winner in loses[i]:
wins[winner] = wins[winner].union(wins[i])
for i in range(1, n+1):
if (len(wins[i]) + len(loses[i])) == (n-1):
answer += 1
return answer
Author And Source
이 문제에 관하여(220324 - 순위), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@skarb4788/220324-순위저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)