220324 - 순위

이상해씨·2022년 3월 24일

알고리즘 풀이

목록 보기

71/94

◾ 순위 : 프로그래머스 LEVEL 3

https://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

◾ 풀이

1. 해설

선수와 경기 결과의 수가 작으므로 전체를 탐색하며 결과를 찾는다.
먼저, 경기 결과에 따라 승, 패에 대한 결과를 추가한다.
추가된 경기 결과에 따라 다른 선수의 결과를 추가한다.
- a 선수의 승리 결과 : b, a 선수의 패배 결과 : c
- b에 속한 선수들은 c에 속한 선수들에게 패배한다.
- c에 속한 선수들은 b에 속한 선수들에게 승리한다.
- set() 자료형을 통해 각 결과에 대해 반복없이 추가한다. - 합집합

2. 프로그램

문제 1

◾ 순위 : 프로그래머스 LEVEL 3

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

문제

입력

선수의 수는 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