사용자 도구

사이트 도구


ps:problems:programmers:85002

복서 정렬하기

ps
링크programmers.co.kr/…
출처프로그래머스
문제 번호85002
문제명복서 정렬하기
레벨Level 1
분류

기초

시간복잡도O(n^2)
인풋사이즈n<=1000
사용한 언어Python
해결날짜2021/09/07

풀이

  • 그냥 시키는대로, 주어진 정렬 기준에 해당되는 값을 계산해서 정렬하면 된다
  • 한 선수의 승률을 계산하기 위해서는, n명의 선수와의 전적을 봐야 하므로 O(n). 따라서 n명의 선수 모두에 대해서 승률을 각각 구하려면 O(n^2). {자신보다 무거운 복서를 이긴 횟수} 를 모든 선수에 대해서 구하는 것도 마찬가지로 O(n^2).
  • 정렬 기준을 다 계산하는 데에 O(n^2). 정렬하는 것은 O(nlogn). 그러므로 전체 복잡도는 O(n^2)

코드

"""Solution code for "Programmers 85002. 복서 정렬하기".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/85002
- Solution link: http://www.teferi.net/ps/problems/programmers/85002
"""


def solution(weights, head2head):
    def compare_key(num):
        my_weight, my_h2h = weights[num - 1], head2head[num - 1]
        win_count, loss_count = my_h2h.count('W'), my_h2h.count('L')
        win_rate = (0 if win_count == 0
                    else win_count / (win_count + loss_count))
        win_against_heavier_count = sum(1 for w, h in zip(weights, my_h2h)
                                        if h == 'W' and w > my_weight)
        return (-win_rate, -win_against_heavier_count, -my_weight, num)

    return sorted(range(1, len(weights) + 1), key=compare_key)

토론

댓글을 입력하세요:
H S L M U
 
ps/problems/programmers/85002.txt · 마지막으로 수정됨: 2021/09/13 14:37 저자 teferi