Tutorial : STL Sort 2 ( 정렬 기준 설정 ) timer 2s memory 1024MB

앞선 문제에서는 sort 함수의 기본 사용법을 익혔다.

이젠 조금 더 어려운 정렬을 해볼 것이다.

from functools import cmp_to_key

# left < right -> return 음수
# left == right -> return 0
# left > right -> return 양수 (정렬을 할 때 swap)
def comp(left, right):
    if  left[1] != right[1]:
        return -1 if left[1] < right[1] else 1
    if  left[0] != right[0]:
        return -1 if left[0] < right[0] else 1
    return 0

A = [ ("Bob", 15), ("Alice", 15), ("Ellie", 13) ]
A.sort(key = cmp_to_key(comp))

def priority(x):
    return ( x[1], x[0] )

A = [ ("Bob", 15), ("Alice", 15), ("Ellie", 13) ]
A.sort(key = priority)

<퀴즈>

배열의 정수들을 "일의 자리 숫자를 기준으로" 정렬해보자.

만약 일의 자리 숫자가 동일한 것들이 여러 개라면, 이들끼리는 "크기를 기준으로" 정렬한다.

즉, 정렬 기준의 1 순위가 "일의 자리 숫자"가 되고, 2 순위가 "크기" 가 되는 것이다.

예를 들면, 배열 A가 아래처럼 정렬되기를 원하는 것이다.

배열 A에서 오른쪽으로 갈수록,

일의 자리 숫자가 커지고, ( 1 순위 정렬 기준 )

일의 자리 숫자가 같은 것들끼리는 크기를 기준으로 정렬한 것이다. ( 2 순위 정렬 기준 )

아래 코드를 보면서 이해해보자.

#include <algorithm>
using namespace std;

// Left : 배열에서 왼쪽에 있는 수
// Right : 배열에서 오른쪽에 있는 수
bool comp ( int Left , int Right ){
    // 일의 자리 숫자가 다르다면 ?
    // 1 순위 정렬 기준 : 일의 자리 숫자로 비교
    if((Left % 10) != (Right % 10)){ 
        return (Left % 10) < (Right % 10);
    }
    // 일의 자리 숫자가 같았다면? 
    // 2 순위 정렬 기준 : 크기로 비교
    return Left < Right;
}

int main(){
    int i;
    int A[7] = {16, 28, 8, 6, 3, 26, 83};
    sort( A + 0 , A + 7 , comp); //  A = [ 3, 83, 6, 16, 26, 8, 28 ]
}

main 함수를 보면,

sort 함수 뒤에 인자가 하나 더 추가되어 있다. ( sort( A + 0 , A + 7 , comp ); )

뒤에 추가하는 bool 타입의 comp 함수는 두 수를 받아와서, 사용자가 설정한 정렬 기준을 바탕으로 비교하여 그 결과를 return 한다.

이를 직관적으로 이해하는 방법은 아래와 같다.

그림에서 보면, 배열에서 "오른쪽으로 갈수록 일의 자리 숫자가 커진다"는 것을 알 수 있다.

comp 함수에서 받아온 두 수를 Left 와 Right 로 이름을 지으면 이해하기 쉽다.

( 다른 변수 이름도 가능하다. 다만 이해를 돕기 위해 이렇게 이름을 지은 것이다. )

Left 는 배열에서 왼쪽에 있는 수, Right 는 배열에서 오른쪽에 있는 수다.

오른쪽으로 갈수록 일의 자리 숫자가 커져야 하므로, Left 보다 Right 의 일의 자리 숫자가 더 커야 한다.

그러므로 comp 함수 안에 이 코드가 적힌 것이다.

return (Left % 10) < (Right % 10);

여기에 이제 1 순위, 2 순위 정렬 기준만 넣어주면 된다.

1 순위 정렬 기준은 "일의 자리 숫자" 이다.

즉, Left 와 Right 의 일의 자리 숫자가 다르다면, 무조건 "일의 자리 숫자" 를 기준으로 둘을 비교하는 것이다.

만약 이 둘의 일의 자리 숫자가 같다면, 그 때 2 순위 정렬 기준인 "크기"를 기준으로 비교한다.

따라서 최종 comp 함수는 아래와 같다. 맨 처음 코드에 이를 설명하는 주석이 있으니 잘 읽어보자.

이 내용 만큼은 완벽하게 이해하고 다음으로 넘어가는 것이 중요하다.

몇 번 읽어봐도 이해가 가지 않는다면, 주변 선생님들께 적극적으로 질문하자.

bool comp ( int Left , int Right ){
    if((Left % 10) != (Right % 10)) return (Left % 10) < (Right % 10);
    return Left < Right;
}

<응용 문제>

N 개의 세 자리 정수들을 입력 받고, 이들을

1 순위 : 일의 자리 숫자

2 순위 : 십의 자리 숫자

3 순위 : 백의 자리 숫자

를 기준으로 오름차순 정렬해보자.