문제 설명
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위입니다.
👸 나의 풀이
from collections import defaultdict
def solution(n, results):
dic = defaultdict(list) # key:이긴 선수, 값:진 선수
lose=defaultdict(list) # key : 진 선수, 값 : 이긴 선수
result={} # 승부 결과 수
for r in results:
dic[r[0]].append(r[1])
lose[r[1]].append(r[0])
def dfs(dic, key):
visited[key] = True
for loser in dic[key]:
if not visited[loser]:
dfs(dic, loser)
for key in list(dic.keys()): # 이긴 선수
visited = [0] * (n + 1)
dfs(dic, key)
result[key]=visited.count(True)-1 # 자기 자신은 제외
for key in list(lose.keys()) : # 진 선수
visited=[0]*(n+1)
dfs(lose, key)
try :
result[key]+=visited.count(True)-1
except : # key가 없을 때 발생하는 에러 처리
result[key]=visited.count(True)-1
return list(result.values()).count(n-1)
문제를 이해하면 어렵지 않게 풀 수 있다.
순위를 알려면 총 사람 수 n-1만큼의 결과(이긴 것+진 것)이 있어야함.
key가 이긴 사람과 진 사람인 두 가지 딕셔너리를 만들었다.
dfs로 visited 기록을 한 후 true의 갯수를 센다. 이 갯수는 key가 이긴 사람의 수 또는 진 사람의 수다.
딕셔너리 result에서 총 사람 수n-1의 갯수를 세서 반환한다.
참고로 list(lose.keys())로 써야 RuntimeError: dictionary changed size during iteration가 뜨지 않는다.
# 실패
from collections import defaultdict
def solution(n, results): # 선수의 수, 경기 결과
answer = 0
dic=defaultdict(list)
for value, key in results : # key: 선수, value : key에게 짐
dic[key].append(value)
return answer
딕셔너리에 담아놓고 그 다음에 탐색을 어떻게 해야할지 몰라서 ㅠ
🙋♀️ 다른 사람 풀이
# https://velog.io/@tjdud0123/%EC%88%9C%EC%9C%84-python
def solution(n, results) : # 선수의 수, 경기 결과
chart=[[0]*n for _ in range(n)] # 승패표
WIN, LOSE=1, -1
for i, j in results : # 내입장 win = 상대방 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])
chart=[[0, 1, 0, 0, 0], [-1, 0, -1, -1, 1], [0, 1, 0, -1, 0], [0, 1, 1, 0, 0], [0, -1, 0, 0, 0]]위는 테케의 승패표 예시
스택을 사용해서 DFS 구현.
1. wins에 'chart[me] 선수가 이긴 상대 선수들 번호'를 저장.
2. wins에서 뽑은 '경기에서 진 선수 loser'가 이긴 상대방을 wins에 담는다.
me가 이긴 선수 loser가 이긴 선수 opp는 me 또한 이긴 것으로 기록한다.
정리하면 a를 이긴 사람c는 a에게 진 사람b를 이긴다.
a에게 진 사람c는 a를 이긴 사람b에게 진다.
위 과정 반복
0은 자기 자신이다. 0이 한 개면 순위가 명확하다.
# https://velog.io/@tjdud0123/%EC%88%9C%EC%9C%84-python
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) # a가 b를 이김
loses[b].add(a) # b가 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
loses={3:{4}, 2:{1, 3, 4}, 5:{2}}
wins={4:{2, 3}, 3:{2}, 1:{2}, 2:{5}}위는 테케의 딕셔너리
딕셔너리를 사용한 풀이
'i에게 진 선수 loser에게 진 선수들'과 'i가 진 선수들'을 or연산한다.
2가 5를 이겼으니까 2에게 진 선수들 1, 3, 4가 loses[5]에 추가된다.
'i를 이긴 선수 winner'들과 'i가 이긴 선수들'을 or연산한다.
1이 2를 이겼으니까 2가 이긴 선수 5를 wins[1]에 추가한다.
wins와 loses의 총 길이가 본인을 제외한 총 선수 수와 같으면 등수를 명확히 알 수 있다.
# https://inspirit941.tistory.com/98
def solution(n, results):
# wins[key]=key가 이긴 사람들의 집합
# loses[key]=key가 이기지 못한 사람들의 집합
wins, loses={}, {}
for i in range(1, n+1) :
wins[i], loses[i]=set(), set()
for i in range(1, n+1) : # 1번부터 시작
for battle in results :
if battle[0] == i : # i의 승리
wins[i].add(battle[1])
if battle[1] == i : # i의 패배
loses[i].add(battle[0])
# i를 이긴 사람들 (loses[i]) => i에게 진 사람(wins[i])은 반드시 이긴다
for winner in loses[i] :
wins[winner].update(wins[i])
# i에게 진 사람들(wins[i]) => i를 이긴 사람들(loses[i])에게는 반드시 진다.
for loser in wins[i] :
loses[loser].update(loses[i])
cnt=0
for i in range(1, n+1) :
if len(wins[i])+len(loses[i]) == n-1 :
cnt+=1
return cnt
위 알고리즘과 같다.
딕셔너리를 이용한 풀이.
각 선수의 승리와 패배를 기록한다.
add()는 set의 메소드다.
update()는 딕셔너리에 값 갱신
// https://willbfine.tistory.com/524
import java.util.*;
class Solution {
public int solution(int n, int[][] results) {
int answer = 0;
order=new LinkedList[n];
reverse=new LinkedList[n];
// 메모리 공간 할당
for(int i=0; i<order.length; i++){
order[i]=new LinkedList<>();
reverse[i]=new LinkedList<>();
}
// 값 입력
for(int i=0; i<results.length; i++){
int win=results[i][0]-1;
int lose=results[i][1]-1;
order[lose].add(win);
reverse[win].add(lose);
}
// 함수 호출
for(int i=0; i<n; i++){
int sum=0;
count=0;
visited=new boolean[n];
explore(i, order);
sum=count;
count=0;
visited=new boolean[n];
explore(i, reverse);
sum+=count;
if(sum == n-1) answer++;
}
return answer;
}
boolean[] visited;
List<Integer>[] order;
List<Integer>[] reverse;
int count;
// 재귀호출을 이용한 dfs
private void explore(int v, List<Integer>[] graph){
visited[v]=true;
for(int adj : graph[v]){
if(!visited[adj]){
count++;
explore(adj, graph);
}
}
}
}
진 사람, 이긴 사람 리스트를 만들고 dfs로 수를 센다.
order의 인덱스는 진 사람, reverse의 인덱스는 이긴 사람이다. 각각의 값은 이긴 사람, 진 사람이다.
값을 여러 개 넣어야해서 각 인덱스마다 LinkedList로 공간을 할당해줬다. ArrayList 사용해도 됨.
삽입/삭제 연산은 LinkedList가 ArrayList보다 더 효율적임.
총 사람 수-1이면 순위를 명확히 알 수 있으므로 answer을 증가시킨다.
문제 출처 💁♀️ 프로그래머스
'coding test' 카테고리의 다른 글
| [파이썬, Java] 완주하지 못한 선수 (0) | 2021.04.22 |
|---|---|
| [파이썬] 합승 택시 요금 (0) | 2021.04.20 |
| [파이썬] 등굣길 (0) | 2021.04.18 |
| [파이썬, Java] 입국심사 (0) | 2021.04.17 |
| [파이썬] 여행경로 (0) | 2021.04.17 |