Move Fast

▶ Collections 클래스

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

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

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

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

▶ 정렬(Sorting)

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

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

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

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

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

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

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

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

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

• 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()는 만약 반환값이 양수이면 찾고자 하는 원소의 인덱스값이고, 음수이면 탐색이 실패한 것이다. 즉, 원소를 찾지 못했음을 의미한다.

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

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

▶ 컬렉션

- 컬렉션(Collection) : 자바에서 자료 구조를 구현한 클래스들을 칭하는 용어이다.

- 자료 구조(Data Structure) : 자료를 저장하기 위한 구조이다.

- 대부분의 프로그램은 자료를 저장하여야 하고 따라서 어떤 자료 구조를 사용할 것인지 결정하여야 한다.

- 많이 사용되는 자료 구조로는 리스트(list), 스택(stack), 큐(queue), 집합(set), 해쉬 테이블(hash table) 등이 있다.

▶ 컬렉션의 종류

- 자바는 “컬렉션 인터페이스”와 “컬렉션 클래스“로 나누어서 제공한다.

- 컬렉션 인터페이스를 구현한 클래스도 함께 제공하므로 간단히 사용하거나 각각 필요에 맞추어 인터페이스를 자신의 클래스로 구현할 수도 있다.

- 컬렉션 인터페이스와 컬렉션 클래스는 모두 java.util 패키지에 포함되어 있다.

- 컬렉션 라이브러리들은 모두 “제네릭 기능을 지원”한다.

- 아래는 컬렉션 인터페이스를 간단히 설명한 것이다.

- 자바 버전 1.2이전에는 Vector, Stack, HashTable, Bitset, Enumberation 클래스만 제공하였다.

- 자바 버전 1.2이후에는 위의 기재한 클래스 외에 다양한 클래스를 제공되며, 인터페이스와 구현을 분리하였다.

▶ Collection 인터페이스

[인터페이스의 계층 구조]

- 모든 컬렉션 인터페이스의 부모 인터페이스에 해당된다.

- 즉, 모든 컬렉션 클래스들이 Collection 인터페이스를 구현하고 있으므로 Collection에 들어 있는 메소드들은 거의 대부분 컬렉션 클래스에서 사용할 수 있다.

- Collection 인터페이스가 제공하는 메소드