Today's Algorithm(2018-10-12)

programmers 가장 큰 수

정렬 카테고리에 있던 문제 중 하나입니다. 어제 도전을 하였다가 어떤 식으로 구현해야할지 방향이 안나와 다른 사람의 풀이를 참고하였습니다. 다른 사람들의 풀이를 보다가 공통적인 부분을 하나 발견을 했는데요. '정렬 부분에 대한 로직을 Overriding하여 재구현한다'는 것이었습니다. 이 부분이 어떻게 구현되어 있는지 살펴보다가 흥미로운 개념 2개를 발견하였는데요. 그건 바로 Comparable과 Comparator라는 개념입니다.

구글링하여 찾아보니 이 두 개념에 대한 비교는 바늘과 실처럼 항상 따라다니더라구요. 오늘은 Comparator에 대해 가볍게 알아보고 다음 인터페이스에 대한 개념을 자세히 다르게 되면 같이 비교하도록 하겠습니다. 왜냐하면 Comparable은 인터페이스이고 Comparator는 클래스이기 때문입니다.

 

Comparator

Comparator는 정렬이 가능한 클래스(예를들어 ArryList, Arrays 등)에서 기본 정렬 질서와 다르게 구현하고 싶을 때 사용할 수 있습니다. 이번 문제에서 구현한 부분을 보면서 설명하도록 하겠습니다.

   Collections.sort(numbersText, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                if(o1.charAt(0) == o2.charAt(0)) {
                    int aa = Integer.parseInt(o1 + o2);
                    int bb = Integer.parseInt(o2 + o1);
                    return bb-aa;
                }
                return o2.charAt(0) - o1.charAt(0);
            }
        });

수 배열의 각 값에 대한 String값을 ArrayList에 저장을 했었는데요. 그 부분이 numberText 입니다. 보통 이러한 Collections에 대한 정렬은 Collections.sort()을 많이 이용을 하는데요. 이 부분에서 두번째 인자에 Comparator 익명 클래스를 이용하여 실제 정렬 로직 메서드인 compare메서드를 Override합니다. 이 compare메서드 Override 하기 이해하기 위해선 기존이 어떻게 작동하고 있는지 알아야 합니다.

public static int compare(int x, int y) {
        return (x < y) ? -1 : ((x == y) ? 0 : 1);
}

이 부분은 Integer타입일 경우의 compare메서드가 구현된 부분인데요(비록 이번 비교값은 String이지만 비슷한 로직으로 구현되기 때문에 가져왔습니다) 이 메서드의 반환값에 따라 자리바꿈 여부를 결정하게 됩니다. return값이 음수이거나 0일 경우는 자리가 바뀌지 않고 양수일 경우에만 자리가 바뀝니다. 그리고 만약 내림차순으로 정렬하고 싶다면 매개변수 위치만 바꾸면 됩니다.(삼중 연산자에서 true에 앞에고 false가 뒤인거 아시죠? 전 거꾸로 알고있었네요... )

본론으로 다시 돌아가 구현된 코드를 다시보면 우선 if(o1.charAt(0) == o2.charAt(0))에서 각 문자열의 첫번째 Character 타입을 비교합니다. 만약 같다면(예를들어 "21", "24") 앞뒤 조합으로 만든 후("2124", "2421") 이를 int 형으로 바꾸고 비교를 합니다. 자료구조 내에 ["21", "24"] 이런 식으로 있었다면 어떻게 값이 반환될까요?

엥? o1은 "21"이고 o2 "24"이니까 aa는 2124가 되고 bb는 2421 이 되니까 반환값이 양수. 즉 오름차순으로 되어있으니까 자리 바뀌어선 안되는데 바뀌게 되는데??

네.. 저도 이 부분이 헷갈려서 테스트를 해보니 실제 자료구조 내에 ["21", "24"] 순서대로 들어있더라도 메서드 호출시엔 매개변수 o1이 "24", o2가 "21"로 들어가더라구요. 그렇게 된다면 음수가 되고 자리가 안 바뀐다는 것을 알 수 있습니다. 마지막 return o2.charAt(0) - o1.charAt(0)에 대해서도 똑같이 각 문자열의 첫번째 값 차이에 따른 반환값으로 의도에 맞게 정렬하도록 할 수 있습니다.

 

나름 머리속으로 정리되었다고 생각했는데 또 다시 설명하려니 헷갈리고 헤매였네요. 자주 사용되는 개념인만큼 이 글을 자주 참고하면서 익혀야겠습니다. 참 이 부분과 관련해서 이 블로그에서 내용 참고를 하였습니다. 혹시 좀 더 자세하게 알고싶은 분들은 이 블로그 방문하셔서 보시는 것도 좋을 것 같습니다.