다중 정렬을 단일 정렬로 바꿔보자

1. 문제

 

복서 선수들의 몸무게 weights와 복서 선수들의 전적을 나타내는 head2head가 매개변수로 주어집니다.

 

복서 선수들의 번호를 다음과 같은 순서로 정렬한 후 return하도록 solution 함수를 완성해주세요

 

1. 전체 승률이 높은 복서의 번호가 앞쪽으로 갑니다. 아직 다른 복서랑 붙어본 적이 없는 복서의 승률은 0%로 취급합니다.

 

2. 승률이 동일한 복서의 번호들 중에서는 자신보다 몸무게가 무거운 복서를 이긴 횟수가 많은 복서의 번호가 앞쪽으로 갑니다.

 

3. 자신보다 무거운 복서를 이긴 횟수까지 동일한 복서의 번호들 중에서는 자신 몸무게가 무거운 복서의 번호가 앞쪽으로 갑니다.

 

4. 자기 몸무게까지 동일한 복서의 번호들 중에서는 작은 번호가 앞쪽으로 갑니다.

 

2. 제한사항

 

 

3. 예시

 

그림1. 예시1

 

그림2. 예시2

 

4. 나의 풀이

 

문제가 복잡해보여서 풀기 싫어지지만

 

입출력 예시1 설명을 보면 NLWL이나 WNLL이나 LWNW 이런것들이 그냥 그대로 생각하면 된다는거 쉽게 파악가능

 

 

그러면 head2head에서 하나씩 빼서 승률을 계산해야하는데

 

N인 경우는 총 게임에서 계산을 안하는데…

 

단순히 weight의 길이-1이 총 게임이라고 생각하면 안되는 것이

 

3번째 예시를 보면 전부 NNN이라서 head2head에서 하나씩 빼서 하나씩 계산하는게 나을것 같더라

 

def solution(weights, head2head):
    
    answer = []
    
    win_rate = []
    
    for ind, results in enumerate(head2head):
        
        win = 0
        
        total = 0
        
        heavy = 0
        
        weight = weights[ind]

 

head2head에서 하나씩 뺄건데

 

win은 해당 복서의 승리 수

 

total은 총 게임 수

 

heavy는 자신보다 무거운 몸무게를 가진 복서를 이긴 횟수

 

weight는 현재 복서의 몸무게

 

heavy와 weight가 동일 승률일때 정렬기준이 되기때문에 구해야함

 

for opp,result in enumerate(results):
    
    if result == 'W':
        
        win += 1
        
        total += 1
        
        if weight < weights[opp]:
            
            heavy += 1
            
    elif result == 'L':
        
        total += 1
        
    else:
    
        pass

 

위에서 언급한대로 이제 results에서 하나씩 빼서 total, win을 셀거임

 

W이면 승리이니까 win에 1을 더하고 total에도 1을 더해줘

 

근데 자신보다 몸무게가 무거운 사람을 이긴 경우가 중요하니까

 

자기 몸무게는 weight에 저장되어 있고

 

상대방 몸무게는 weights[opp]로 구할 수 있어서 if weight<weights[opp]:라는 새로운 조건 추가해서

 

조건이 맞으면 heavy에 1을 더해줘

 

L이면 진게임이니까 win에는 안더하고 total에만 더해줘

 

N이면 게임을 안한거니까 total에도 안더해야해서 그냥 pass

 

if total != 0:
    
    win_rate.append(((win/total), heavy, weight, ind))
    
else:
    
    win_rate.append((0.0,heavy,weight,ind))

 

total이 0인 경우와 0이 아닌 경우로 나눠서 0이 아니면 승률을 계산할 수 있으니까

 

승률, heavy, weight,ind를 원소로 가지는 tuple을 win_rate에 넣어줘

 

total이 0인 경우는 승률을 0으로 계산하니까 승률은 0으로 하고 똑같이 나머지 원소 tuple로 해서 넣어주고

 

answer = [ans[3]+1 for ans in sorted(win_rate,
                                      key=lambda item: [-item[0],-item[1],-item[2],item[3]])]

return answer

 

앞에서 배웠던 정렬기술을 활용해서 정렬을 수행할거임

 

win_rate에서 sorted를 할건데 key로 정렬조건을 준다

 

win_rate의 원소는 0번이 승률 1번이 자기보다 무거운 몸무게를 가진 복서를 이긴 횟수, 2번이 자기 몸무게, 3번이 자기 번호

 

먼저 승률이 가장 높은 복서의 번호가 앞쪽으로 가니까 승률을 기준으로 내림차순 정렬

 

그런데 승률도 동일하면

 

자기보다 몸무게가 무거운 복서를 이긴 횟수가 많은 복서의 번호가 앞쪽으로 가니까 heavy를 기준으로 내림차순 정렬

 

heavy조차도 동일하면

 

몸무게가 무거운 복서가 앞쪽으로 가니까 몸무게 weight 기준으로 내림차순 정렬

 

몸무게조차도 동일하면

 

복서 번호가 작은 번호가 앞쪽으로 가니까 복서 번호는 오름차순 정렬

 

이런 정렬 기준은 key=lambda item : [-item[0],-item[1],-item[2],item[3]]을 이용하면 가능!

 

이렇게 정렬한 리스트에서 원소를 하나씩 뺀 다음

 

중요한건 복서 번호 index니까 ans[3]을 가져와서 새로운 리스트에 넣는 list comprehension 사용

 

문제 인덱스는 1번부터 시작하니까 ans[3]+1을 넣어줘야함

 

 

5. 다른 풀이

 

좋아요를 가장 많이 받은 풀이는…

 

def solution(weights, head2head):
    
    result = []
    
    l = len(weights)
    
    ans = [[0 for _ in range(4)] for _ in range(l)]

 

몸무게의 길이를 먼저 구해서 l에 저장하고

 

ans에 빈 리스트를 만들건데

 

승률, 자기보다 무거운 복서를 이긴 횟수, 자기 몸무게, 번호 4개를 리스트로 원소로 가지는 이중리스트 ans 생성

 

for i in range(l):
    
    ans[i][2] = weights[i]
    
    ans[i][3] = -(i+1)
    
    cnt = 0

 

result에서 W,N,L 빼서 하는게 아니라 앞에서 구한 길이 l에서 for문을 돌리네?

 

그러면 일단 몸무게랑 자기 번호는 ans에 넣을 수 있음

 

번호를 음수로 넣는 이유는 나머지는 내림차순으로 정렬할때 얘는 오름차순으로 정렬시킴

 

for j in rnage(l):
    
    if head2head[i][j] == 'W':
        
        ans[i][0] += 1
        
        cnt += 1
        
        if weights[i] < weights[j]:
            
            ans[i][1] += 1
            
    elif head2head[i][j] == 'L':
        
         cnt += 1

 

뭐야? 나랑 다를게 없네… 나는 result에서 W,N,L 빼서 했지만… 비슷비슷하네

 

W면 승리수, 판수 더해주고 자기보다 몸무게가 무거운 경우는 몸무게가 무거운 사람 이긴 수 더해주고

 

L이면 판수만 더해주고

 

    if cnt == 0:

        ans[i][0] = 0

    else:

        ans[i][0] /= cnt
    
ans.sort(reverse=True)

for i in range(l):
    
    result.append(-ans[i][3])
    
return result

 

판수가 0이면 승률을 0으로 계산하고 판수가 0이 아니면 승률을 구해서 승률로 넣어주고

 

마지막에 reverse=True로 해서 한번에 정렬해버리네

 

이게 번호를 -를 붙여서 넣었기때문에 가능

 

나도 저렇게 하면 간단하게 바꿀 수 있겠는데?

 

그림3. 번호를 음수로 넣어서 간단하게 바꿔본 코드

 

6. 되돌아보기

 

앞에서 배웠던 다중정렬하기  key=lambda item : [-item[0],-item[1],-item[2],item[3]] 이거 활용한거 아주 좋았다

 

문제가 복잡해보이더라도 입출력 예시라든지 잘 활용하면 쉽게 보일 수도 있다는거 기억해야하고

 

다중정렬 할수도 있지만 필요없는 원소, 예를 들어 번호에 -1을 붙여서 넣어서 한번에 단일정렬시킬수도 있다는거