반응형

 7월 18일에 제가 운영한 2회 코딩테스트가 열렸습니다. 이 중에, 1번 문제는 다중 정렬을 이용한 문제였습니다. 백준에서 정렬 분류로 치면 나오는 문제들을 풀 수 있다면 풀 수 있게 해서 그런지, 정답자 수가 많은 편에 속하는 문제가 되었습니다. 그 이후에도 사람들이 꾸준히 많이 풀어주셨는데요.

 

 저는 name과 확장자, os에서 확장자를 인식하는지 여부를 3개의 플래그로 만들어서 관리했습니다. 그런데, 다른 분이 Comparator와 람다를 잘 이용하면, 코드도 줄일 수 있고, 단순화 된다는 조언을 주셨습니다.

 


 먼저, myFile 클래스를 보겠습니다. name과 ext만 필드에 있습니다. 생성자는 name과 ext를 받아서, 확장자와 네임을 생성이 될 때 채워넣습니다. 그 이후로 setName, setExt 같은 것이 없으니 동결 되게 됩니다.

 

 

 그리고 eSet에는 제가 설치한 os에서 인식하는 확장자를 넣게 됩니다.

 

 

 핵심이 되는 부분은 35번째 줄부터 37번째 줄입니다. Comparator는 보통 정렬 기준이 있는 경우에 또 다른 정렬 기준을 쓰려고 많이 씁니다. 이 포스팅에서 한 번 언급을 했었습니다. 예를 들어, String을 다른 기준으로, 사전 역순으로 정렬하고 싶을 때 써먹을 수 있습니다.

 

 여기서 중요한 건, Comparator의 comparing인데요. 메서드 참조, 람다 등을 받았음을 알 수 있습니다.

 

 해당 메서드의 내부를 보면, keyExtractor.apply(c1)이 있는데요. keyExtractor는 키 값을 뽑아내는 용도로 쓰는 함수적인 인터페이스 정도로 이해하시면 됩니다. 그런데, keyExtractor가 왜 2개가 있는가?

 

 compareTo는 왜 키 2개를 비교하는가? 간단합니다. timSort도 비교 기반 정렬이기 때문입니다. 비교 기반이 대체 뭐지? 이 글에서 간단하게 설명하고 있지만, 저 글까지 보는 수고를 덜어드리기 위해서 한 번 더 설명해 보겠습니다. count sort는 잘 생각해 봅시다. 두 개의 키를 비교하지는 않아요.

 

 단지, 키 값과 대응되는 위치에 count를 하나 더 시킬 뿐입니다. 반면에, 비교 기반은 다릅니다. 병합 정렬을 예로 들면

 

 2개의 정렬된 sub array가 있어요. 이것을 merge 시키는 과정이 정복 과정입니다. 이 과정에서 처음에 1과 2를 비교합니다. 오름차순으로 정렬한다면, 1이 2보다는 앞에 와야 하니까, 1을 합쳐진 배열에 먼저 넣습니다.

 

 

 다음에, 3과 2를 비교하게 됩니다. 2개의 키를 비교하게 되니, 비교 기반 정렬입니다. comparing 메소드를 보면 keyExtractor를 넘기게 되는데요.

 

 

 이 keyExtractor는 키 값을 뽑기 위한 Function 인터페이스입니다. 이걸 람다로 처리한 것입니다.

 


 이제 myFile::getName의 의미도 이해가 가실 거라 생각합니다. 결국 키를 뽑아내는 myFile::getName을 넘긴 다음에, 결과 값을 가지고 또, thenComparingInt, thenComparing 등으로 체이닝을 시켜 버리는 것입니다. 중요한 것은 getName이나, getExt나 아스키 사전순으로 올리라고 하였으니, 복잡하게 처리할 이유는 없습니다. 만약에 아스키 역순이였다면 이야기가 달라질 수도 있습니다.

 

 예를 들어, 파일 이름은 아스키 내림차순으로 정렬하고 싶다면 아래와 같이 코딩하시면 됩니다.

 

 뭔가 복잡해 보이지만 사실 별 건 없습니다.

 

 보시면 2번째 인자가 keyComparator인데요. 키를 sort 하기 위한 Comparator를 넘겨줍니다.

 

 실행 결과는 위와 같습니다.

반응형

댓글을 달아 주세요