Sorting: Comparator

2021-06-16 1052 words 3 minutes

Contents

두 개 이상의 조건을 반영한 sorting 문제이다.

Problem

Comparators are used to compare two objects. In this challenge, you’ll create a comparator and use it to sort an array. The Player class is provided in the editor below. It has two fields:

name: a string
score: an integer

Given an array of $n$ Player objects, write a comparator that sorts them in order of decreasing score. If 2 or more players have the same score, sort those players alphabetically ascending by name. To do this, you must create a Checker class that implements the Comparator interface, then write an int compare(Player a, Player b) method implementing the Comparator.compare(T o1, T o2) method. In short, when sorting in ascending order, a comparator function returns $-1$ if $a < b$, $0$ if $a=b$, and $1$ if $a>b$.

문제는 일상생활에서도 자주 접할 법한 상황에 대해 보여준다. 점수순으로 sorting하고 동점자 간에는 가나다순으로 정렬하는 일은 충분히 살면서 마주할만한 문제이다. 문제의 구성을 보면 Java를 기준으로 출제된 문제라는 것을 알 수 있는데 이 문제를 Python의 형태로 문제코드를 구성한 것도 흥미로웠다.

아래가 문제코드이다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

n = int(input())
data = []
for i in range(n):
    name, score = input().split()
    score = int(score)
    player = Player(name, score)
    data.append(player)
    
data = sorted(data, key=cmp_to_key(Player.comparator))
for i in data:
    print(i.name, i.score)

Line 7까지는 그냥 instance를 만들어 리스트에 넣어주는 것이며 line 9에서 sorting이 이루어진다. 여기서 특정 값을 기준으로 할 때 보통 key에 lambda함수를 넣어주는데 여기서는 두 개의 조건을 반영해야하다보니 lambda함수로 사용하기가 어렵다. 즉 key값을 lambda로 간단하게 쓰기는 어렵고 함수의 형태로 표현할 것이므로 이를 처리해주는 wrapper가 필요해지고 이를 cmp_to_key가 하게된다.

cmp_to_key는 아래와 같이 생겼다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

def cmp_to_key(mycmp):
    'Convert a cmp= function into a key= function'
    class K:
        def __init__(self, obj, *args):
            self.obj = obj
        def __lt__(self, other):
            return mycmp(self.obj, other.obj) < 0
        def __gt__(self, other):
            return mycmp(self.obj, other.obj) > 0
        def __eq__(self, other):
            return mycmp(self.obj, other.obj) == 0
        def __le__(self, other):
            return mycmp(self.obj, other.obj) <= 0
        def __ge__(self, other):
            return mycmp(self.obj, other.obj) >= 0
        def __ne__(self, other):
            return mycmp(self.obj, other.obj) != 0
    return K

문제푸는거야 주어진 클래스의 comparator만 입력하면 되지만 문제를 검사하는 함수가 어떻게 작동하는 지 알려면 위의 함수를 이해하여야 한다. mycmp는 self.obj와 비교대상인 other.obj를 arugment로 하는 함수이고 풀려고 하는 문제상황에서는 data안에 있는 Player각 각각 self와 other에 들어가 비교될 것이다.

Answer

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Player:
    def __init__(self, name, score):
        self.name = name
        self.score = score
    def __repr__(self):
        return repr((self.name, self.score))
    
    def comparator(a, b):
        names = [a.name, b.name]
        name_sorted = False
        if names == sorted(names):
            name_sorted = True

        if (a.score > b.score):
            return -1
        if (a.score < b.score):
            return 1
        if (a.score == b.score):  # a.score == b.score
            if name_sorted:
                return -1
            else:
                return 1

Explanation

두 개의 조건을 비교하는 문제이므로 우선 비교 대상의 이름이 알파벳순인지를 먼저 확인해다. sorted는 편리하게도 string끼리의 비교에서는 알파벳순으로 처리해준다.

문제에서 설명하였듯, 점수에 대해서는 내림차순이므로 앞의 a가 b의 score보다 크면 -1로 앞으로 오게 된다. 동점일 때는 알파벳순으로 정렬되어있다면 그대로 사용하지만, 그렇지 않다면 순서를 바꾸도록 설정해주었다.

Reference

HackerRank