프로그래머스: 순위 python, 파이썬

1. 문제

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

코딩테스트 연습 - 순위

2. 풀이

이 분의 아이디어를 읽고 구현했다.

내 언어로 설명해보자면,

 

1) 주어진 값 넣기: 먼저 n*n 배열을 만들고, 배열[이긴사람][진사람]에 1(이김) 배열[진사람][이긴사람]에 -1 짐을 넣는다.

여기서 중요한 건 몇등이냐가 아니라 모든 다른 사람에 대해 내 결과를 가지고 있는 사람이 몇사람이냐는 것이다.

 

2) 배열을 채운다:  이제 배열을 순회하면서 A가 B를 이겼다면 B에게 진 사람들은 A에게 모두 졌을 것이라고 생각하고 이것을 채워넣는다. 마찬가지로 A가 C에게 졌다면 C를 이긴 사람들의 정보를 채운다. 여기서 주의할 점은 A가 B에게 진경우 B의 값을 채울 때 b,c의 정보를 넣었다면 c,b의 정보도 넣어줘야 모든 값을 다 넣는 것이 된다. vise versa 값을 잊지 말고 모두 넣자.

 

3) 답을 센다:  자기 자신인 경우를 건너뛰고, 값이 채워지지 않으면 break로 나가고 break하지 않은 행은 answer+=1해준다.

 

https://velog.io/@e7838752/boj2458

[백준] 2458번. 키 순서

 

 

3. 구현

def solution(n, results):
    answer = 0
    INF = -1*100000
    mp=[[INF for _ in range(n+2)] for __ in range(n+2)]
    
    for a,b in results:
        mp[a][b]=1
        mp[b][a]=-1
    
    for a in range(1, n+1):
        for b in range(1, n+1):
            if mp[a][b]==1:
                for idx, score in enumerate(mp[b]):
                    if score==1:
                        mp[a][idx]=1
                        mp[idx][a]=-1
            elif mp[a][b]==-1:
                for idx, score in enumerate(mp[b]):
                    if score==-1:
                        mp[a][idx]=-1
                        mp[idx][a]=1
    # print(mp)
    for a in range(1,n+1):
        breakFlag=False
        for b in range(1,n+1):
            if a==b:
                continue
            if mp[a][b]==INF:
                breakFlag=True
                break
        if breakFlag==False:
            answer+=1
            
    return answer