파이썬 문자열 다중정렬 : sort가 stable 하다는 것을 이용합시다.

 저번 시간에 tuple을 이용해서 다중 정렬을 손쉽게 하는 법을 배웠습니다. 특히 정수는 오름차순 반대인 내림차순으로 비교하기 위해서, 앞에 -만 붙이면 매우 간단하게 비교할 수 있어요. 그런데 문자열은 그게 되지 않습니다. 문제 상황을 보면서 어떻게 구현하면 좋을지 천천히 생각해 보도록 합시다.

 

 개인적으로 아래 두 개의 글을 먼저 보고 오시는 게 좋아 보입니다.

 

[관련글]

tuple로 정렬 기준을 떨어트리는 방법을 알아봅시다.

안정 정렬에 대해서 알아봅시다.

 

---

 solution 함수를 구현해야 하는데요. list에는 튜플이 들어 있어요. 튜플의 1번째, 2번째 요소는 소문자로만 이루어진 문자열이 들어 있어요. 1차 정렬 기준은, 1번째 요소를 사전순 내림차순으로 돌립니다. 만약에, 1번째 요소가 같은 문자열이라면 2번째 요소가 사전순 오름차순이 되게끔 sort를 해야 해요.

 

 처음 solution 함수는 아래와 같은 포맷으로 주어질 거에요. 입출력 예제를 볼까요?

 

 

 li와 li2는 input을 의미해요. 우리는 여기서 solution 함수를 잘 구현해서, 우리가 원하는 기능을 구현해야 해요. 당연하게도, 그냥 솔루션 함수에 추가적인 것을 구현하지 않으면, 잘못된 결과가 나오겠죠?

 

 

 어떻게 해야 올바르게 정렬할 수 있을까요? 답은 2번 정렬하는 것이다. 입니다. 이는 제가 개최한 모의 코딩테스트를 보신 분이 블로그에 언급한 22232번 풀이와 동일합니다. 이 글을 보셨다면 아. 이런 풀이로도 풀 수 있구나 정도만 짚고 넘어가셨을 텐데요. 왜 그 풀이가 되는지 아는 것이 중요하다고 생각해요. 그것을 이해하려면 정렬에 대한 깊은 이해가 필요합니다.

 

 

---

 먼저 파이썬의 sort는 timsort를 씁니다. stable sort를 쓰는데요. 우선 순위가 같은 데이터에 대해서 정렬 후의 결과가 바뀌지 않습니다. 예를 들어 아래 데이터가 있었다고 해 보겠습니다.

 

 정렬 전에 이런 식으로 데이터가 있었다고 해 보겠습니다. 위에 있는 수를 오름차순으로 정렬할 거에요. lo라고 표시한 것은, 정렬 전에 있었던 위치 정보를 의미합니다.

 

 

 정렬 후에 요래 되면, 안정 정렬입니다. 어떻게 되었나요? 같은 우선순위를 가지는 것에 대해서, 상대적인 location 순서가 바뀌지 않았어요. 물론, 이러한 사전 지식 없이도, 파이썬의 sorted가 안정 정렬인지, 그렇지 않은지 손쉽게 아는 방법이 있는데요.

 

 

 (1, 100), (1, 99), ... 순으로 리스트 li에 데이터가 들어갔습니다. sorted에서 tuple의 1번째 원소를 기준으로 정렬하는데요. 1번째 원소는 모두 1이니 모든 튜플의 우선 순위 자체는 같아요. 따라서, 정렬 후에도 원본 순서를 유지하고 있으면 stable 한 것인데요.

 

 

 (1, 100), (1, 99), ... 순으로 정렬되었음을 확인할 수 있어요. stable sort인 셈입니다. 간단하게 안정 정렬인지 확인하는 방법이니까 메모해 두시면 좋겠습니다. 어찌 되었던 이러한 특성 때문에, 정렬 기준 역순으로 정렬을 하면 손쉽게 목적을 달성할 수 있어요. 제약 조건대로 들어오는지 확인하는 assert 같은 것을 이용하면 금상첨화일 듯 하네요.

 

---

 코드를 보겠습니다. 

 

 먼저, 2번째 요소인 k[1]을 기준으로 오름차순 정렬을 합니다. 다음에, 정렬된 list를 다시, 1번째 요소인 k[0]을 기준으로 정렬하는데요. 이 때, reverse=True로 셋팅하면, 오름차순이 아닌 사전순 내림차순으로 정렬하게 되어요.

 

 

 정렬이 잘 되었네요. 1번째 요소 기준으로는 내림차순, 2번째 기준으로 오름차순이니까 잘 된 거겠죠? 왜 잘 동작할까요? 간단합니다. 일단, 1번째 요소 기준 상관없이 2번째 요소 오름차순으로 정렬되었다면 아래와 같이 sort가 되었을 겁니다.

 

 

 그림에서 O는 tuple의 1번째 요소, T는 2번째 요소를 나타냅니다. 이제, 2번째로 sort를 할 때, 첫 번째 요소를 기준으로 sort가 될 텐데요. 1번째 요소가 다른 경우에는 별 문제가 되지 않습니다. 그런데, 둘이 같은 경우가 문제가 될 수 있어요. 예를 들자면 이런 경우입니다.

 

 군청색으로 칠한 것들 끼리, 노란색으로 칠한 것들끼리가 문제가 된다는 이야기입니다. 그런데 잘 생각해 보면, 2번째로 정렬하기 전에, 이미 2번째 요소 오름차순으로 정렬이 되어 있었습니다. 1', 2', 3'은 사전순으로 1', 2', 3' 순으로 된다는 의미입니다. 따라서, 같은 우선순위인 것들이 정렬 전과 정렬 후에 배열 순서가 바뀌지 않으면 요런 식으로 상황이 그려질 겁니다.

 

 

 2번째 요소에 대해서 오름차순으로 정렬했다는 정보가, 1번째 요소가 같을 때 보존되게 됩니다. 따라서, 올바른 결과가 나옵니다. k개의 정렬 기준에 대해서도 동일한 기법을 쓸 수 있을까요? 1번 기준, 2번 기준, ... k번 기준 이렇게 k개의 기준이 있을 때. 이것도 조금만 생각해 봅시다. 2번, ... , k번 기준으로 정렬한 결과가 아래와 같다고 해 보자고요.

 

 2번부터 k번 기준까지 고려해서 정렬한 결과입니다. other를 주목해서 보시면 됩니다. 그 다음에 1번 기준으로 정렬하면 아래와 같이 될 텐데요.

 

 

 O=1이 O=2보다는 앞에 왔어요. 첫 번째 기준이 다른 경우는 별 다른 문제가 되지는 않지만, 문제는 이 1번째 기준이 같은 경우인데요. 이 때에는 2 ~ k번 기준에 따라서 순서가 부여된 other가 있어요. 이 순서가 1번째 기준인 O가 같은 경우에는 바뀌지 않았어요. 그래서, 정렬 order 역순으로 돌려도 됩니다.

 

 이 문제에서 확장자, 지원여부, 파일명 순서대로 정렬을 3번 하는 풀이가 맞은 이유는, 정렬 기준이 파일명, 지원여부, 확장자 순이였기 때문입니다. 그리고 python의 sorted가 stable 했기 때문입니다. how to sort 문서에도 나와 있으니 천천히 읽어보시는 게 좋겠습니다.