[Java] 컬렉션 기반 알고리즘 (sort, binarySearch, copy)

collections 클래스에는 다양한 알고리즘을 구현한 메소드들이 존재한다. 이중 일부를 공부해보려고 한다.

 

정렬 메소드 (sort)

public static <T extends Comparable<T>> void sort(List<T> list)

• List<E> 인터페이스를 구현한 클래스들은 저장된 인스턴스를 정렬된 상태로 유지하지 않는다.
• 정렬을 원한다면 sort 메소드를 사용하면 된다.
• 코드 분석
  • public static <T> void sort(List<T> list)
    • 제네릭 메소드로, 메소드 호출 시점에 T가 결정된다.
    • 인자로 List<T>의 인스턴스라면 모두 전달 가능하다.
  • public static <T extends Coparable<T>> void sort (List<T> list)
    • 이때 T는 Comparable<T> 인터페이스를 구현한 상태여야 한다.

public class SortCollections {
    public static void main(String[] args) {
        List<String> list = Arrays.asList("Toy", "Box", "Robot");
        list = new ArrayList<String>(list);

        // 정렬 이전 출력
        for(Iterator<String> itr = list.iterator(); itr.hasNext();)
            System.out.print(itr.next() + " ");
        System.out.println();

        // 정렬
        Collections.sort(list);

        // 정렬 이후 출력
        for(Iterator<String> itr = list.iterator(); itr.hasNext();)
            System.out.print(itr.next() + " ");
    }
}

// 실행 결과
Toy Box Robot 
Box Robot Toy

• T가 String 클래스라면, T의 제약사항이 있기 때문에 확인이 필요하다.
  • Comparable<T>의 T도 String이 될 것이며 즉, String이 Comparable<String>을 구현하고 있어야 한다.
  • String 클래스는 Comparable을 구현하고 있으므로 T로 올수 있음을 확인할 수 있다.
    → class String extends Object implements Comparable<String>
• String 클래스의 compareTo 메소드는 사전순으로 정렬되도록 구현되어 있으므로 사전 순을 기준으로 오름차순 정렬된 결과를 확인할 수 있다.

 

sort() 파헤치기

위에서 sort 메소드를 소개했는데, 사실 실제 sort()는 다음과 같다.

public static <T extends Comparable<? super T>> void sort(List<T> list)

<? super T> 선언이 붙는 이유가 무엇일까?

 

public static <T extends Comparable<T>> void sort(List<T> list)

• List<Car> 인스턴스를 인자로 전달하며 sort()를 호출한다면
• Car는 Comparablc<Car>를 구현해야 한다.

Car를 상속하는 ECar를 정의한다면 ?

class Car implements Comparable<Car> {...}
class ECar extends Car {...}

• ECar는 Car를 상속하므로 Coparable<Car>를 간접 구현한다.
• 하지만 T가 ECar일 경우, ECar는 Comparable를 구현해야 한다.
• 때문에 List 인스턴스를 인자로 전달하며 sort 호출이 불가능하다.

이때 <? super T> 선언이 붙으면 ?

public static <T extends Comparable<? super T>> void sort(List<T> list)

• ECar는 Comparable를 구현해야 한다.
• super로 하한제한을 걸어 Comparable의 T는 ECar이거나 ECar가 상속하는 클래스이어야 한다.
• 즉, Coparable
• 따라서 List 인스턴스를 인자로 전달하며 sort 호출이 가능하다.

class Car implements Comparable<Car> {
    private int disp; // 배기량

    public Car(int disp) {
        this.disp = disp;
    }

    @Override
    public String toString() {
        return "cc: " + disp;
    }

    @Override
    public int compareTo(Car o) {
        return disp - o.disp; // 오름차순
    }
}

public class Collections_Sort_Car {
    public static void main(String[] args) {
        List<Car> list = new ArrayList<>();
        list.add(new Car(1200));
        list.add(new Car(3000));
        list.add(new Car(1800));
        Collections.sort(list); // 정렬

        for (Iterator<Car> itr = list.iterator(); itr.hasNext();)
            System.out.println(itr.next() + " ");
    }
}

// 실행 결과
cc: 1200 
cc: 1800 
cc: 3000

class Car2 implements Comparable<Car2> {
    protected int disp; // 배기량

    public Car2(int d) {
        disp = d;
    }

    @Override
    public String toString() {
        return "cc: " + disp;
    }

    @Override
    public int compareTo(Car2 o) {
        return disp - o.disp; // 오름차순
    }
}

class ECar extends Car2 { // 전기 자동차를 표현한 클래스
    private int battery;  // 배터리

    public ECar(int d, int b) {
        super(d); // 상위 클래스 생성자 호출
        battery = b;
    }

    @Override
    public String toString() {
        return "cc: " + disp + ", ba: " + battery;
    }
}

public class Collections_Sort_ECar {
    public static void main(String[] args) {
        List<Car2> list = new ArrayList<Car2>();
        list.add(new ECar(1200, 99));
        list.add(new ECar(3000, 55));
        list.add(new ECar(1800, 87));
        Collections.sort(list); // 정렬

        for(Iterator<Car2> itr = list.iterator(); itr.hasNext();) // 출력
            System.out.println(itr.next() + " ");
    }
}

// 실행 결과
cc: 1200, ba: 99 
cc: 1800, ba: 87 
cc: 3000, ba: 55

 

Comparator 기반 정렬

public static <T> void sort(List<T> list, Comparator<? super T> c)

• Collections 클래스에는 다음과 같은 sort() 메소드도 정의되어 있다.
• 이는 호출시 정렬의 기준을 결정할 수 있는 형태로 정의된 메소드이다.
• <? super T> 의미
  • 매개변수 c를 대상으로는 T형 인스턴스를 넣는(전달하는) 메소드 호출만 허용
  • Car의 정렬을 위해 정의한 클래스의 인스턴스를 대상으로 ECar도 정렬 가능 (아래 예제 참고)

class Car {
    protected int disp; // 배기량

    public Car(int d) {
        disp = d;
    }

    @Override
    public String toString() {
        return "cc: " + disp;
    }
}

// Car의 정렬을 위한 클래스 정의
class CarComp implements Comparator<Car> {
    @Override
    public int compare(Car o1, Car o2) {
        return o1.disp - o2.disp;
    }
}

class ECar extends Car {
    private int battery; // 배터리

    public ECar(int d, int b) {
        super(d);
        battery = b;
    }

    @Override
    public String toString() {
        return "cc: " + disp + " ,ba: " + battery;
    }
}


class SortCollections_Car_Comparator {
    public static void main(String[] args) {
        List<Car> clist = new ArrayList<Car>();
        clist.add(new Car(1800));
        clist.add(new Car(1200));
        clist.add(new Car(3000));

        List<ECar> elist = new ArrayList<ECar>();
        elist.add(new ECar(3000, 55));
        elist.add(new ECar(1800, 87));
        elist.add(new ECar(1200, 99));

        CarComp comp = new CarComp();

        // 각각 정렬
        Collections.sort(clist, comp);
        Collections.sort(elist, comp); // 이 문장이 이 예제의 핵심 !

        for (Iterator<Car> itr = clist.iterator(); itr.hasNext();)
            System.out.println(itr.next() + " ");
        System.out.println();

        for (Iterator<ECar> itr = elist.iterator(); itr.hasNext();)
            System.out.println(itr.next() + " ");
    }
}

// 실행 결과
cc: 1200 
cc: 1800 
cc: 3000 

cc: 1200 ,ba: 99 
cc: 1800 ,ba: 87 
cc: 3000 ,ba: 55

• 위 예제에서 List<ECar>형 인스턴스로 sort가 가능한 이유는 다음과 같다.
  • sort 메소드의 두번째 매개변수가 Comparator<? super T>이기 때문이다.
  • 따라서 T가 ECar일 경우, Comparator<? super T>의 T로 올수 있는 것은 ECar이거나 ECar가 상속하는 클래스이다.
    • Comparator<Object>
    • Comparator<Car>
    • Comparator<ECar>
  • 여기서 ECar는 Car를 상속한다. 즉, ECar는 Comparator<Car>를 간접구현하므로 정렬이 가능한 것이다.

 

 

찾기 메소드 (binarySearch)

public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key)

• 리스트 자료구조를 기반으로 특정 인스턴스를 찾을 때 사용
  • list에서 key를 찾아 그 인덱스 값을 반환
  • 못 찾으면 음의 정수 반환
• 코드 분석
  • public static <T> int binarySearch(List<?>list, T key)
    • 첫번째 인자로 List<E> 인스턴스는 무엇이든 올 수 있다.
  • public static <T> int binarySearch(List<? extends Comparable<T>>list, T key)
    • 단, 이때 E는 Comparable<T>를 구현해야 한다.
  • public static <T> int binarySearch(List<? extends Comparable<? super T>>list, T key)
    • 이때 T는 T이거나 T가 상속하는 상위클래스이어야 한다.
• binarySearch 메소드는 이진 탐색 알고리즘을 기반으로 탐색을 진행한다. 따라서 정렬된 상태이어야 동작한다.
  • 이진탐색은 정렬된 리스트 자료구조를 대상으로 적용하는 알고리즘이기 때문

class BinarySearchCollections_String {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("Box");
        list.add("Robot");
        list.add("Apple");

        Collections.sort(list); // 정렬
        int idx = Collections.binarySearch(list, "Robot"); // 탐색

        System.out.println(idx + ". " + list.get(idx)); // 탐색 결과 출력
    }
}

// 실행 결과
2. Robot

 

Comparator<T> 기반 찾기

public static <T> int binarySearch(List<? extends T> list, T key, comparator<? super T> c)

• Collections 클래스에는 Comparator<T>를 구현하는 클래스를 정의하여 탐색 기준을 마련할 수 있는 다음 메소드도 존재한다.
• list에서 key를 찾는데 c의 기준을 적용하여 찾는다.
• 코드 분석
  • public static <T> int binarySearch(List<T> list, T key, Comparator<T> c)
  • public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c)
    • list에서 T형 인스턴스를 꺼내는 것만 허용
    • c에 T형 인스턴스를 넣는(전달하는) 것만 허용
    • Comparator<? super T>의 T는 T이거나 T의 상위클래스가 올 수 있다.

// String 정렬 및 탐색을 위한 클래스 정의
class StrComp implements Comparator<String> {
    @Override
    public int compare(String s1, String s2) {
        return s1.compareToIgnoreCase(s2); // 대문자, 소문자 구분 없이 비교
    }
}

class BinarySearchCollections_String_Comparator {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("ROBOT");
        list.add("APPLE");
        list.add("BOX");

        StrComp comp = new StrComp(); // 정렬과 탐색의 기준

        Collections.sort(list); // 정렬
        int idx = Collections.binarySearch(list, "Robot", comp); // comp 기준을 적용해 탐색

        System.out.println(idx + ". " + list.get(idx)); // 탐색 결과 출력
    }
}

// 실행 결과
2. ROBOT

 

 

복사 메소드 (copy)

public static <T> void copy(List<? super T> dest, List<? extends T> src) // src의 내용을 dest로 복사

• 리스트 구조의 컬렉션 인스턴스에 저장된 내용을 복사하는 기능의 메소드이다.
• 메소드 호출 시 매개변수 dest에 전달되는 컬렉션 인스턴스의 저장 공간이 src에 전달되는 컬렉션 인스턴스의 저장 공간보다 크거나 같아야 한다.
  
  • dest 공간이 더 작다면 복사 과정에서 예외가 발생한다.
• 이미 생성된 컬렉션 인스턴스의 내용을 통째로 바꾸려는 경우에 copy 메소드가 유용하게 사용된다.
• <? super T>인 이유 ? dest에 T형 인스턴스를 넣는 것만 허용하겠다. 꺼내면 컴파일 에러
• <? extends T>인 이유 ? src로부터 T형 인스턴스 꺼내는 것만 허용하겠다. 넣으면 컴파일 에러

class CopyCollections {
    public static void main(String[] args) {
        List<String> src = Arrays.asList("Box", "Apple", "Toy", "Robot");

        // 복사본 만들기
        List<String> dest = new ArrayList<>(src);

        // 정렬하여 결과 출력
        Collections.sort(dest);
        System.out.println(dest);

        // dest에 저장된 내용을 src에 저장된 내용으로 덮어씀
        Collections.copy(dest, src);

        // 확인
        System.out.println(dest); // 컬렉션 인스턴스에 저장된 내용 전부 출력
    }
}

// 실행 결과
[Apple, Box, Robot, Toy]
[Box, Apple, Toy, Robot]