[프로그래머스][LV.3] 순위 | python3

문제링크:  순위

---

문제설명

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-1 (자기자신을 뺀 값) 이어야 함.

def solution(n, results):
    answer = 0
    
    # rank={i:i for i in range(1,n+1)} 
    # a를 이기면 a가 이긴 사람들까지 이기는 것.
    
    win=[[i] for i in range(n+1)]
    lose=[[i] for i in range(n+1)]
    
    for w,l in results:
        win[w].append(win[l])
        lose[l].append(lose[w])
        
    for i in range(n+1):
        if len(win[i])+len(lose[i])==n-1:
            answer+=1
    
    return answer

 

프로그래머스 내의 ai 답변 : 사용자가 작성한 코드의 문제점은 `win`과 `lose` 리스트에 바로 이긴 사람들과 진 사람들을 추가하는 방식입니다. 이 방법은 만약 A가 B를 이기고 B가 C를 이기면 A가 C를 이겼다는 관계가 반영되지 않습니다. 즉, 간접적인 승패 관계가 고려되지 않은 것이 문제입니다.

이를 해결하기 위해서는 각 선수가 이긴 사람과 진 사람의 리스트를 업데이트할 때, 이미 리스트에 추가된 사람들의 승패 관계까지 고려하여 업데이트해야 합니다. 즉, `win[w].append(win[l])`과 `lose[l].append(lose[w])` 부분에서 단순히 리스트를 추가하는 것이 아니라, 리스트 내의 각 요소를 확인하고 간접적인 승패 관계까지 포함시켜 업데이트해야 합니다. 이를 위해선 리스트를 합치는 방식을 재고하고, 각 선수가 이기거나 진 모든 상대를 정확하게 파악할 수 있는 로직으로 수정해야 할 것입니다. 또한, 이긴 사람과 진 사람을 처리할 때 중복을 피하기 위한 추가적인 조치가 필요합니다.

 

저 append 부분에서 추가해준건데...

=> append는 이중 리스트가 될 위험이 있음. extend로 원소 추가만 해줘야함. => 리스트일때

중복 제거를 위해 set을 사용해야 하며 set은 update로 원소 추가

 

 

i에게 이긴 번호들은 i가 이긴 번호들에게도 이긴다,

i에게 진 번호들은 i가 진 번호들에게도 진다.

나의코드

def solution(n, results):
    answer = 0
    
    # rank={i:i for i in range(1,n+1)} 
    # a를 이기면 a가 이긴 사람들까지 이기는 것.
    
    win=[set() for _ in range(n+1)]
    lose=[set() for _ in range(n+1)] # 자기자신은 추가할 필요 없음
    
    
    for w,l in results:
        win[w].add(l)
        lose[l].add(w)
        
    for i in range(1,n+1):
        for w in lose[i]: # w : i를 이긴 번호들
            win[w].update(win[i]) # win[i] -> i가 이긴 번호들
        for l in win[i]: # l : i에게 진 번호들
            lose[l].update(lose[i]) # lose[i] -> i가 진 번호들
        
        
    # 결과
    for i in range(n+1):
        if len(win[i])+len(lose[i])==n-1:
            answer+=1
    
    return answer코드

 

 

---

 

 

참고하기

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

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

    for result in results:
        total[result[0]-1][result[1]-1] = 'WIN'
        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] == 'WIN' and total[k][j] == 'WIN':
                    total[i][j] = 'WIN'
                elif total[i][k] == 'LOSE' and total[k][j] == 'LOSE':
                    total[i][j] = 'LOSE'

    answer = 0

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

    return answer