42. Collection Class - 컬렉션 클래스

▶ Collections 클래스

 

- Collections 클래스는 여러 유용한 알고리즘을 구현한 메소드들을 제공한다.

 

- 이 메소드들은 제네릭 기술을 사용하여 작성되었으며 정적 메소드의 형태로 되어있다.

 

- 자주 사용되는 알고리즘으로는 정렬(Sorting), 섞기(Shuffling), 탐색(Searching) 등이 있다. 

• 언급한 세 메소드의 첫 번째 매개변수는 알고리즘이 적용되는 컬렉션이다.

https://docs.oracle.com/javase/7/docs/api/java/util/Collections.html

 

 

 

▶ 정렬(Sorting)

 

- 데이터를 어떤 기준에 의하여 순서대로 나열하는 알고리즘이다.

- 퀵 정렬, 합병 정렬, 히프 정렬 등의 다양한 방법이 존재한다.

- Collections 클래스의 정렬은 속도가 비교적 빠르고 안전성이 보장되는 합병 정렬을 이용한다.

- 안전성이란 동일한 값을 가지는 원소를 다시 정렬하지 않는 것을 의미한다.

- 안전성은 같은 리스트를 반복하여 다른 기준에 따라 정렬할 때 중요하다.

 

 예를 들어 상품 주문 리스트를 날짜를 기준으로 먼저 정렬하고 이후 주문처를 기준으로 정렬한다면 사용자는 같은 주문처가 보낸 주문은 날짜별로 정렬될 것이라고 가정한다. 이처럼 한번 정렬된 것이 유지되는 경우를 안정성 있는 정렬이라고 말한다.

 

- Collection 클래스의 sort() 메소드는 정적메소드로, List 인터페이스를 구현하는 컬렉션에 대하여 정렬을 수행한다.

 

List<String> list = new LinkedList<String>();

list.add(“김철수”);

list.add(“김영희”);

Collections.sort(list);

 

 위의 경우는 원소가 String 타입이므로 알파벳 순서대로 정렬될 것이다. 원소가 Date 타입이라면 시간적인 순서로 정렬될 것이다. 그 이유는 String 클래스와 Date 클래스 모두 Comparable 인터페이스를 구현하기 때문이다.

 

- 정렬은 Comparable 인터페이스를 이용하여 이루어진다. List 인터페이스는 Comparable 인터페이스를 상속하므로

 

public interface Comparable<T> {

public int comparaTo(T o);

}

• comparaTo() 메소드는 매개변수 객체를 현재의 객체와 비교하여 작으면 음수, 같으면 0, 크면 양수를 반환한다.

- 예제 1

import java.util.*;

public class SortTest1 {
    public static void main(String[] args) {
        String[] example = { "Nice", "to", "meet", "you" };
        List<String> list = Arrays.asList(example); //배열을 리스트로 무조건 변환!
        Collections.sort(list); //리스트 정렬

        System.out.println(list);
    }
}

[예제 1 출력 결과]

meet과 to의 위치가 바뀐 것을 볼 수 있다. 알파벳순이기 때문에 이러한 결과가 나온 것이다.

- 예제 2

import java.util.*;

class Student implements Comparable<Student> {
    int number;
    String name;

    Student(int number, String name) {
        this.number = number;
        this.name = name;
    }

    public String toString() {
        return name;
    }

    @Override
    public int compareTo(Student s) {
        return number - s.number; //학번순서로 정렬한다.
    }
}

public class SortTest2 {
    public static void main(String[] args) {
        Student[] students = {
            new Student(02, "선옥자"),
            new Student(03, "한영희"),
            new Student(01, "김철수")
        };

        List<Student> list = Arrays.asList(students);
        Collections.sort(list);
        System.out.println(list);
    }
}

[예제 2 출력 결과]

- 예제 3 : 역순으로 정렬하기 - Collections.sort(list, Collections.reverseOrder());

import java.util.*;

public class SortTest {
    public static void main(String[] args) {
        String[] example = { "Nice", "to", "meet", "you" };
        List<String> list = Arrays.asList(example); //배열을 리스트로 무조건 변환!
        Collections.sort(list, Collections.reverseOrder()); //리스트 역순정렬

        System.out.println(list);
    }
}

 [예제 3 출력 결과]

 역순정렬로 인해 예제 1의 출력 결과와 반대되는 결과를 볼 수 있다.

▶ 섞기(Shuffling)

 

- 리스트에 존재하는 정렬을 파괴하여서 원소들의 순서를 랜덤하게 만든다.

 

- 정렬과는 반대 동작을 한다.

 

- 주로 게임을 구현할 때 유용하게 쓰인다. 예를 들어 카드 게임에서 카드를 섞을 때 사용할 수 있다.

- 예제

import java.util.*;

public class Shuffle {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<Integer>();

        for(int i = 0; i <= 10; i++) {
            list.add(i);
        }

        Collections.shuffle(list);
        System.out.println(list);
    }
}

 [출력 결과 1]

[출력 결과 2]

메소드를 실행할 때마다 서로 다른 출력 결과를 보인다.

 

 

▶ 탐색(Searching)

 

- 리스트 안에서 원하는 원소를 찾는 알고리즘이다.

 

- 선형 탐색 : 처음부터 모든 원소를 방문하는 탐색 방법으로, 리스트가 정렬되어 있지 않은 경우 사용한다.

 

- 이진 탐색 : 리스트가 정렬되어 있는 경우 중간에 있는 원소(m)와 먼저 비교하여, 크면 그다음부(m+1)터 끝까지 비교하고, 작으면 처음부터 그 전(m-1)까지의 원소들과 비교하는 방식을 반복하여 하나의 리스트를 계속해서 두 개의 리스트로 분할한다. 이 방법은 리스트에 하나의 원소가 남을 때까지 반복된다. 이진 탐색은 문제의 크기를 반으로 줄일 수 있기 때문에 선형 탐색보다 효율적이다.

 

- Collections 클래스는 정렬된 리스트에서 지정된 원소를 이진 탐색한다. 

- 이진 탐색 메소드인 binarySearch()는 만약 반환값이 양수이면 찾고자 하는 원소의 인덱스값이고, 음수이면 탐색이 실패한 것이다. 즉, 원소를 찾지 못했음을 의미한다.

 

int index = Collections.binarySearch(list, element);

// list는 리스트, element는 탐색할 원소이다.

 

 단, binarySearch() 메소드는 실패하더라도 도움이 되는 정보를 반환한다. 즉, 반환값에는 현재의 데이터가 삽입될 수 있는 위치 정보가 있다. 반환값이 pos라고 한다면, (-pos-1)이 해당 데이터를 삽입할 수 있는 위치이다.

 

int pos = Collections.binarySearch(list, key);

if(pos < 0) list.add(-pos-1);

 

- binarySearch() 메소드는 위에도 언급했듯이 “정렬된 리스트”에 한해서 탐색을 진행한다는 점에 주의하여야 한다.