파이썬 다중정렬 : tuple을 이용한 dsu 패턴으로 간단하게 처리합시다.

 제가 개최한 코딩 테스트 후기 글들을 꾸준히 보고 있는데요. 이 글들을 잘 보면, 생각보다 배울 만한 것들이 많았습니다. 제가 낸 문제 중에, 가희와 파일 탐색기가 있었는데요. 이 글에서는 풀이 보다는 정렬 조건이 복잡할 때, 아 이러한 패턴이 있었구나. 정도만 알고 넘어가셔도 괜찮겠다 싶어서 가지고 오게 되었습니다. 사실 이 글에서 언급하는 방법 말고도 우선순위 역순으로 n회 정렬한다던지와 같은 방법도 있는데, 이에 대해서는 나중에 언급할 기회가 있을 듯 싶어요.

 

---

 dsu 패턴은 생각보다 복잡하지 않아요. python에서는 여러 비교 기준이 있는 문제에서 tuple을 이용하게 됩니다. dsu는 3가지 과정으로 나뉩니다. 먼저, 데이터를 가공합니다. 어떻게 가공해야 할까요? list나 tuple은 문서에 따르면, 사전순으로 앞선 것이 앞에 온다는 조건이 붙어 있어요.

 

 예를 들어 봅시다.

 

 target에는 4개의 tuple이 들어 있어요. 이것을 정렬해 볼게요. 어떻게 나올까요?

 

 

 사전순으로 정렬됨을 알 수 있어요. 1번째가 같으면 2번째 사전순으로, 2번째까지 같으면, 3번째 원소 사전순으로 정렬이 되게 됩니다. 이를 응용하면, 기준이 3개 있다면, 우선 순위가 가장 높은 기준을 tuple의 0번째, 다음 기준을 tuple의 1번째, 그 다음 기준을 2번째로 넣어버리면 됩니다. 즉, 가공할 때에는 tuple로 가공한다. 가 정답이겠네요.

 

 22232번 문제를 보겠습니다.

 

 어떻게 tuple에 넣으면 될까요? 파일명, os가 인식하는 확장자인지에 대한 정보, 확장자명 이런 순서대로 넣으면 됩니다. 이것까지 반영한 것을 코드에 넣어 보겠습니다.

 

 

 먼저, files는 파일명과 확장자가 tuple 형태로 들어와 있어요. 다음에 dic은 입력받은 확장자, 즉 os에서 인식하는 확장자 명들만 들어 있어요. 먼저 가공하라고 했으니까, deco 배열로 가공 처리해 봅시다.

 

 

 sorted 안에 있는 부분을 잘 보세요. 보시면 배열 안에 [k[0], k[1] not in dic, k[1]] 이렇게 가공했음을 볼 수 있는데요. files에 있는 원소의 0번째 요소가 파일명이고, 1번째 요소가 확장자이기 때문입니다. 그런데 k[1] not in dic은 무엇을 의미할까요? os에서 인식하는 확장자라면 False가 리턴되고, 인식하지 못하는 것이라면 True가 리턴됩니다. False가 True보다 사전순으로 뒤에 있음을 이용한 것입니다. 이렇게 가공된 배열을 sorted로 정렬했습니다.

 

 그 다음에 8번째 줄에, 정렬된 가공된 배열을 통해서, 원래 배열로 복원하게 됩니다. 이를 Undecorate 과정이라고 합니다. Decorate, Sort, Undecorate. 이렇게 세 과정을 줄여서 DSU pattern이라고 이야기 합니다.

 

 

 실행 결과는 위와 같습니다. 핵심은 tuple로 deco를 하였다는 것입니다. 최근 트렌드는 lambda와 keys를 이용해서 sort를 하는 것입니다만, tuple로 떨어트리는 전략은 유효합니다.

 

---

 이 패턴을 잘 이용하면, 복잡해 보이는 제 cpp 코드도 리팩토링 할 수 있습니다. 원리는 같습니다. 정렬하기 위해 가공 처리를 하고, 가공된 것들을 정렬한다. 먼저 c++에 tuple이 추가되었으니, 이것을 잘 이용해 봅시다.

 

 

 똑같은 방법으로 접근하시면 되는데요. files는 파일명과 확장자 묶음의 list로 저장합니다. 다음에 deco는, files를 정렬하기 위해서 강제로 tuple에 들어가는 순서를 조정하는, 가공된 list입니다. 파일명, 파일 확장자가 os에서 인식하는지, 그리고 확장자 순으로 넣을 겁니다.

 

 

 입력 받는 부분이니까 이 부분은 넘어가 봅시다.

 

 

 deco에, os가 인식하는 확장자인지 넣었다는 점이 중요한데요. 이렇게 전처리를 하면, compare 과정에서 확장자가 os에 있는지를 검사할 필요가 없습니다. 단지 1과 0만 가지고 비교하면 됩니다.

 

 

 실행 결과는 위와 같습니다. 정렬을 쉽게 하기 위해서 tuple로 가공시킨 다음에 sort를 시키는 기법은 코테에서 많이 쓰이니 알아두시면 좋겠습니다.