2019년 6월 12일 수요일

Java Comparator 인터페이스를 이용한 숫자 정렬






* Comparator 이용하여 숫자 정렬하기


Comparator 인터페이스, compare 메소드, Array sort, API 문서 참고: 
https://docs.oracle.com/javase/7/docs/api/index.html?overview-summary.html


문제는 아래와 같이 주어진 String 문자열들을 내림차순으로 정렬해야 하는데 000.000 같은 경우 0.0으로 출력되면 안되고, 반드시 형태를 유지해야한다.

[sample input]

9
-100
50
0
56.6
90
0.12
.12
02.34
000.000




class Solution{
    public static void main(String []args){
        //Input
        Scanner sc= new Scanner(System.in);
        int n=sc.nextInt();
        String []s=new String[n+2];
        for(int i=0;i<n;i++){
            s[i]=sc.next();
        }
        sc.close();

        Arrays.sort(s,0,n, Collections.reverseOrder(new Comparator<String>() {
            @Override
            public int compare(String a1, String a2) {
                BigDecimal a = new BigDecimal(a1);
                BigDecimal b = new BigDecimal(a2);
                return a.compareTo(b);
            }
        }));
        //Output
        for(int i=0;i<n;i++)
        {
            System.out.println(s[i]);
        }
    }
}
기존 String 배열을 재정렬하는 부분의 코드를 분석해보자.

먼저 Array.sort로 들어오는 인자를 보면, s String 배열을 0번째부터 n번째까지 Comparator의 정렬 기준으로 정렬한다. n은 포함이 아니다.
Comparator 객체를 다시한번 reverseOrder 를 하여 문제가 요구하는대로 내림차순이 되도록 하였다.

Comparator 객체를 생성하면서 동시에 compare메소드를 오버라이드(재정의) 하여 새로운 정렬 기준을 작성한다.
BigDecimal 클래스를 이용하여 String 형으로 되어있는 숫자를 변환하였고, 0의 손실이 일어나지 않도록 하였다.
또한 BigDecimal 클래스의 compareTo 메소드는 a가 b보다 앞서있는 경우에는 음수를, 동일하면 0, a가 b보다 뒤에있다면 양수를 반환한다. 
그래서 이 메소드가 반환하는 값이 Comparator클래스에서 compare 메소드의 return 값이 된다.
BigDecimal의 compareTo 메소드는 Comparator에서 구현해야하는 compare의 조건과 일치한다.
Comparator 클래스에서 오버라이드를 하는 compare 메소드에는 주의해야 할 필수 조건이 있다.

1. sgn(compare(x,y)) 가 -sgn(compare(y,x))와 같아야 한다는 것이다.

* sgn?
In the foregoing description, the notation sgn(expression) designates the mathematical signum function, which is defined to return one of -1, 0, or 1 according to whether the value of expression is negative, zero or positive.

2. ((compare(x, y)>0) && (compare(y, z)>0)) 로부터 compare(x, z)>0 을 추정할 수 있어야 한다.
3. sgn(compare(x, z))==sgn(compare(y, z)) for all z 라면, 이것으로부터 compare(x, y)==0 임을 알 수 있어야 한다.

위 조건을 반드시 만족하도록 compare 메소드를 오버라이드 시켜야 제대로 된 정렬이 일어날 것이다.

댓글 없음:

댓글 쓰기