[Java/김영한] 순회, 정렬

https://inf.run/sDjcZ

김영한의 실전 자바 - 중급 2편| 김영한 - 인프런 강의

이 링크를 통해 구매하시면 제가 수익을 받을 수 있어요. 

 

 

순회

자료 구조에서 순회는 자료 구조에 들어있는 데이터를 차례대로 접근해서 처리하는 것을 말한다. 그런데 다양한 자료 구조가 있고, 각각의 자료 구조마다 데이터를 접근하는 방법이 모두 다르다.

 

자바는 자료 구조의 구현과 관계 없이 모든 자료 구조를 동일한 방법으로 순회할 수 있게 `Iterable`과 `Iterator` 인터페이스를 제공한다.

 

 

Iterable, Iterator

• `Iterable`: 반복 가능한
• `Iterator`: 반복자

public interface Iterable<T> {
      Iterator<T> iterator();
}

• 단순히 `Iterator` 반복자를 반환

 

public interface Iterator<E> {
      boolean hasNext();
      E next();
}

• `hasNext()`: 다음 요소가 있는 지 확인. 다음 요소가 없으면 `false`를 반환
• `next()`: 다음 요소를 반환. 내부에 있는 위치를 다음으로 이동한다.

 

직접 구현

클래스 구조도

 

public class MyArrayIterator implements Iterator<Integer> {

    private int currentIndex = -1;
    private int[] targetArr;

    public MyArrayIterator(int[] targetArr) {
        this.targetArr = targetArr;
    }

    @Override
    public boolean hasNext() {
        return currentIndex < targetArr.length - 1;
    }

    @Override
    public Integer next() {
        return targetArr[++currentIndex];
    }
}

• 생성자를 통해 반복자가 사용할 배열을 참조

public class MyArray implements Iterable<Integer> {

    private int[] numbers;

    public MyArray(int[] numbers) {
        this.numbers = numbers;
    }

    @Override
    public Iterator<Integer> iterator() {
        return new MyArrayIterator(numbers);
    }

}

• `Iterable` 인터페이스 구현
  • 이 자료 구조에 사용할 반복자(`Iterator`)를 반환
  • 이때 `MyArrayIterator`는 생성자를 통해 `MyArray`의 내부 배열인 `numbers`를 참조

 

public class MyArrayMain {

    public static void main(String[] args) {
        MyArray myArray = new MyArray(new int[]{1, 2, 3, 4});

        Iterator<Integer> iterator = myArray.iterator();
        System.out.println("iterator 사용");
        while (iterator.hasNext()) {
            Integer value = iterator.next();
            System.out.println("value = " + value);
        }
    }

}

 

실행 결과

iterator 사용 
value = 1 
value = 2 
value = 3 
value = 4

 

 

 

 

 

자바의 제공

• 자바는 컬렉션 프레임워크를 사용하는 개발자가 편리하고 일관된 방법으로 자료 구조를 순회할 수 있도록 `Iterable` 인터페이스를 제공하고, 이미 각각의 구현체에 맞는 `Iterator`도 다 구현해두었다.
  
  • 자바 `Collection` 인터페이스 상위에 `Iterable` 존재 → 모든 컬렉션을 `Iterable`, `Iterator`를 사용해서 순회 가능
• `Map`의 경우, `Key`와 `Value`가 있어서 바로 순회X
  • 대신 `Key`나 `Value`를 정해서 순회할 수 있다.
  • `keySet()` → `Set` 반환, `values()` → `Collection` 반환, `entrySet()` → `Entry`를 `Set`으로 반환

---

향상된 for문

자바는 `Iterable` 인터페이스를 구현한 객체에 대해서 향상된 for문을 사용할 수 있게 해준다.

for (int value : myArray) {
      System.out.println("value = " + value);
}

 

이렇게 하면 자바는 컴파일 시점에 다음과 같이 코드를 변경한다.

while (iterator.hasNext()) {
      Integer value = iterator.next();
      System.out.println("value = " + value);
}

따라서 두 코드는 같은 코드이다. 데이터를 순회한다면 둘 중에 깔끔한 향상된 for문을 사용하는 것이 좋다.

---

정렬

기본 클래스

public class SortMain1 {

    public static void main(String[] args) {
        Integer[] array = {3, 2, 1};
        System.out.println(Arrays.toString(array)); // [3, 2, 1]

        System.out.println("기본 정렬 후");
        Arrays.sort(array);
        System.out.println(Arrays.toString(array)); // [1, 2, 3]
    }
}

 

`Arrays.sort()`를 사용하면 배열에 들어있는 데이터를 순서대로 정렬할 수 있다.

 

비교자 - Comparator

1, 2, 3 순서가 아니라 반대로 정렬하고 싶으면 이때 비교자(`Comparator`)를 사용하면 된다.

 

두 값을 비교할 때 비교 기준을 직접 제공할 수 있다.

public interface Comparator<T> {
      int compare(T o1, T o2);
}

• 두 인수를 비교해서 결과 값을 반환하면 된다.
  • 첫 번째 인수가 더 작으면 음수
  • 두 값이 같으면 `0`
  • 첫 번째 인수가 더 크면 양수

package collection.compare;

import java.util.Arrays;
import java.util.Comparator;

public class SortMain2 {

    public static void main(String[] args) {
        Integer[] array = {3, 2, 1};
        System.out.println(Arrays.toString(array));
        System.out.println("Comparator 비교");
        Arrays.sort(array, new AscComparator());
        System.out.println("AscComparator:" + Arrays.toString(array));

        Arrays.sort(array, new DescComparator());
        System.out.println("DescComparator:" + Arrays.toString(array));
        Arrays.sort(array, new AscComparator().reversed()); //DescComparator와 같다.
        System.out.println("AscComparator.reversed:" + Arrays.toString(array));
    }

    static class AscComparator implements Comparator<Integer> {
        @Override
        public int compare(Integer o1, Integer o2) {
            System.out.println("o1=" + o1 + " o2=" + o2);
            return (o1 < o2) ? -1 : ((o1 == o2) ? 0 : 1);
        }
    }

    static class DescComparator implements Comparator<Integer> {
        @Override
        public int compare(Integer o1, Integer o2) {
            System.out.println("o1=" + o1 + " o2=" + o2);
            return (o1 < o2) ? -1 : ((o1 == o2) ? 0 : 1) * -1;
        }
    }
}

 

`Arrays.sort()`를 사용할 때, 비교자(`Comparator`)를 넘겨주면 알고리즘에서 어떤 값이 더 큰지 두 값을 비교할 때, 비교자를 사용한다.

Arrays.sort(array, new AscComparator())
Arrays.sort(array, new DescComparator())

 

 

new AscComparator().reversed()

• 정렬을 반대로 하고 싶으면 `reversed()` 메서드를 사용하면 된다.

---

사용자 정의 클래스

자바가 기본으로 제공하는 객체가 아니라 직접 만든 객체를 정렬하려면 내가 만든 두 객체 중 어떤 객체가 더 큰지 알려줄 방법이 있어야 한다. 이때는 객체에 비교 기능을 추가해주는 `Comparable` 인터페이스를 구현하면 된다. 

 

Comparable

public interface Comparable<T> {
      public int compareTo(T o);
}

• 자기 자신과 인수로 넘어온 객체를 비교해서 반환
  • 현재 객체가 인수로 주어진 객체보다 더 작으면 음수
  • 두 객체의 크기가 같으면 `0`
  • 현재 객체가 인수로 주어진 객체보다 더 크면 양수

 

public class MyUser implements Comparable<MyUser> {

    private String id;
    private int age;

    public MyUser(String id, int age) {
        this.id = id;
        this.age = age;
    }

    public String getId() {
        return id;
    }

    public int getAge() {
        return age;
    }

    @Override
    public int compareTo(MyUser o) {
        return this.age < o.age ? -1 : (this.age == o.age ? 0 : 1);
    }

    @Override
    public String toString() {
        return "MyUser{" +
                "id='" + id + '\'' +
                ", age=" + age +
                '}';
    }
}

• `MyUser` 클래스의 기본 정렬 방식을 나이 오름차순으로 정했다.
• `Comparable`을 통해 구현한 순서를 자연 순서(Natural Ordering)라 한다.

 

public class SortMain3 {

    public static void main(String[] args) {
        MyUser myUser1 = new MyUser("a", 30);
        MyUser myUser2 = new MyUser("b", 20);
        MyUser myUser3 = new MyUser("c", 10);

        MyUser[] array = {myUser1, myUser2, myUser3};
        System.out.println("기본 데이터");
        System.out.println(Arrays.toString(array)); // [MyUser{id='a', age=30}, MyUser{id='b', age=20}, MyUser{id='c', age=10}]

        System.out.println("Comparable 기본 정렬");
        Arrays.sort(array);
        System.out.println(Arrays.toString(array)); // [MyUser{id='c', age=10}, MyUser{id='b', age=20}, MyUser{id='a', age=30}]
    }

}

 

 

 

다른 방식으로 정렬

객체가 가지고 있는 `Comparable` 기본 정렬이 아니라 다른 정렬을 추가하고 싶으면 별도의 `Comparator`을 만들어 넘겨주면 된다.

// 아이디를 기준으로 정렬
public class IdComparator implements Comparator<MyUser> {

    @Override
    public int compare(MyUser o1, MyUser o2) {
        return o1.getId().compareTo(o2.getId());
    }
}

System.out.println("IdComparator 정렬");
Arrays.sort(array, new IdComparator());
System.out.println(Arrays.toString(array)); // [MyUser{id='a', age=30}, MyUser{id='b', age=20}, MyUser{id='c', age=10}]

System.out.println("IdComparator().reversed() 정렬");
Arrays.sort(array, new IdComparator().reversed());
System.out.println(Arrays.toString(array)); // [MyUser{id='c', age=10}, MyUser{id='b', age=20}, MyUser{id='a', age=30}]

 

 

 

정리

객체의 기본 정렬 방법은 객체에 `Comparable`를 구현해서 정의한다. 이렇게 하면 객체는 이름 그대로 비교할 수 있는 객체가 되고 기본 정렬 방법을 가진다. 

기본 정렬 외에 다른 정렬 방법을 사용해야 하는 경우, 비교자(`Comparator`)를 별도로 구현해서 정렬 메서드에 전달하면 된다. 이 경우 전달한 `Comparator`가 항상 우선권을 가진다.

자바가 제공하는 `Integer`, `String` 같은 기본 객체들은 대부분 `Comparable`을 구현해두었다.

 

Arrays.sort(array)

• 객체가 가지고 있는 `Comparable` 인터페이스를 사용해서 기본 정렬을 시도

 

Arrays.sort(array, Comparator)

• 정렬 방식을 지정하고 싶다면 인수로 비교자(`Comparator`)를 만들어 넘겨준다.
• 비교자를 전달하면 객체가 기본으로 가지고 있는 `Comparable`을 무시하고, 별도로 전달한 비교자를 사용하여 정렬

 

 

만약 `Comparable`도 구현하지 않고, `Comparator`도 제공하지 않으면 런타임 오류가 발생한다.

java.lang.ClassCastException: class collection.compare.MyUser cannot be cast
to class java.lang.Comparable

---

배열뿐만 아니라 순서가 있는 자료 구조

List

public class SortMain4 {

    public static void main(String[] args) {
        MyUser myUser1 = new MyUser("a", 30);
        MyUser myUser2 = new MyUser("b", 20);
        MyUser myUser3 = new MyUser("c", 10);

        List<MyUser> list = new LinkedList<>();
        list.add(myUser1);
        list.add(myUser2);
        list.add(myUser3);
        System.out.println("기본 데이터");
        System.out.println(list);

        System.out.println("Comparable 기본 정렬");
        list.sort(null);
        //Collections.sort(list);
        System.out.println(list);

        System.out.println("IdComparator 정렬");
        list.sort(new IdComparator());
        //Collections.sort(list, new IdComparator());
        System.out.println(list);
    }

}

 

 

Collections.sort(list)

• 리스트는 순서가 있는 컬렉션이므로 정렬할 수 있다.
• 기본 정렬이 적용된다.
• 객체 스스로 정렬 메서드를 가지고 있는 `list.sort()` 사용 권장
• 별도의 비교자로 비교하고 싶다면 다음 인자에 비교자를 넘기면 된다.
  • `Collections.sort(list, new IdComparator())`

 

list.sort(null)

• 별도의 비교자가 없으므로 `Comparable`로 비교해서 정렬
• 자연적인 순서로 비교
• 자바 1.8부터 사용
• 별도의 비교자로 비교하고 싶다면 인자에 비교자를 넘긴다.
  • `list.sort(new IdComparator())``

 

 

Tree

`TreeSet`과 같은 이진 탐색 트리 구조는 데이터를 보관할 때, 데이터를 정렬하면서 보관하기 때문에 정렬 기준을 제공하는 것이 필수다.

public class SortMain5 {

    public static void main(String[] args) {
        MyUser myUser1 = new MyUser("a", 30);
        MyUser myUser2 = new MyUser("b", 20);
        MyUser myUser3 = new MyUser("c", 10);

        TreeSet<MyUser> treeSet1 = new TreeSet<>();
        treeSet1.add(myUser1);
        treeSet1.add(myUser2);
        treeSet1.add(myUser3);
        System.out.println("Comparable 기본 정렬");
        System.out.println(treeSet1);

        TreeSet<MyUser> treeSet2 = new TreeSet<>(new IdComparator());
        treeSet2.add(myUser1);
        treeSet2.add(myUser2);
        treeSet2.add(myUser3);
        System.out.println("IdComparator 정렬");
        System.out.println(treeSet2);
    }

}

 

 

new TreeSet<>()

• `TreeSet`을 생성할 때 별도의 비교자를 제공하지 않으면 구현한 `Comparable`을 사용한다.

new TreeSet<>(new IdComparator())

• `TreeSet`을 생성할 때 별도의 비교자를 제공하면 `Comparable` 대신 `Comparator`를 사용해서 정리한다.

---

컬렉션 유틸

정렬 메서드

Integer max = Collections.max(list);
Integer min = Collections.min(list);

• `max`: 정렬 기준으로 최대 값을 찾아서 반환
• `min`: 정렬 기준으로 최소 값을 찾아서 반환

Collections.shuffle(list);

• `shuffle`: 컬렉션을 랜덤하게 섞는다.

Collections.sort(list);
Collections.reverse(list);

• `sort`: 정렬 기준으로 컬렉션 정렬
• `reverse`: 정렬 기준의 반대로 컬렉션 정렬

 

 

컬렉션 생성

List<Integer> list = List.of(1, 2, 3);
Set<Integer> set = Set.of(1, 2, 3);
Map<Integer, String> map = Map.of(1, "one", 2, "two");

• `List.of(. . .)`를 사용하면 컬렉션을 편리하게 생성할 수 있다. 단, 이때는 가변이 아니라 불변 컬렉션이 생성된다.
  • `List`, `Set`, `Map` 모두 `of()` 메서드를 지원한다.
• 불변 컬렉션은 변경할 수 없다. 변경 메서드를 호춝하면 `UnsupportedOperationException` 예외가 발생한다.

 

 

불변 컬렉션과 가변 컬렉션 전환

public class ImmutableMain {

    public static void main(String[] args) {
        //불변 리스트 생성
        List<Integer> list = List.of(1, 2, 3);

        //가변 리스트
        ArrayList<Integer> mutableList = new ArrayList<>(list);
        mutableList.add(4);
        System.out.println("mutableList = " + mutableList);
        System.out.println("mutableList class = " + mutableList.getClass()); // mutableList class = class java.util.ArrayList

        //불변 리스트 전환
        List<Integer> unmodifiableList = Collections.unmodifiableList(mutableList);
        System.out.println("unmodifiableList class = " + unmodifiableList.getClass()); // java.util.Collections$UnmodifiableRandomAccessList

        //예외 발생 java.lang.UnsupportedOperationException
        // unmodifiableList.add(5);
    }
}

• 불변 리스트를 가변 리스트로 전환하려면 `new ArrayList<>()`를 사용하면 된다.
• 가변 리스트를 불변 리스트로 전환하려면 `Collections.unmodifiableList()`를 사용하면 된다.
  • 다양한 `unmodifiableXxx()`가 존재한다.

 

 

빈 리스트 생성

public class EmptyListMain {

    public static void main(String[] args) {
        //빈 가변 리스트 생성
        List<Integer> list1 = new ArrayList<>(); 
        List<Integer> list2 = new LinkedList<>();
         
        //빈 불변 리스트 생성
        List<Integer> list3 = Collections.emptyList(); //자바5 
        List<Integer> list4 = List.of(); //자바9
        
        System.out.println("list3 = " + list3.getClass()); // class java.util.Collections$EmptyList
        System.out.println("list4 = " + list4.getClass()); // class java.util.ImmutableCollections$ListN
    }
}

• 빈 가변 리스트는 원하는 컬렉션의 구현체를 직접 생성하면 된다.
• 빈 불변 리스트는 2가지 생성 방법이 있다.
  • `Collections.emptyList()`: 자바 5부터 제공되는 기능
  • `List.of()`: 자바 9부터 제공되는 치신 기능
  • `List.of()`가 더 간결하고, `List.of(1, 2, 3)`도 불변이기 때문에 사용법에 일관성이 있다.

 

 

Arrays.asList()

List<Integer> list = Arrays.asList(1, 2, 3);
List<Integer> list = List.of(1, 2, 3);

• `Arrays.asList()`로 생성된 리스트는 고정된 크기를 가지지만, 요소들을 변경할 수 있다.
  • `set()`을 통해 요소 변경
  • `add()`, `remove()`  같은 메서드를 호출하면 예외가 발생한다.
    • `java.lang.UnsupportedOperationException` 발생
• 고정도 가변도 아닌 애매한 리스트

 

 

멀티스레드 동기화

Collections.synchronizedList(list);

• 일반 리스트를 멀티스레드 상황에서 동기화 문제가 발생하지 않는 안전한 리스트로 만들 수 있다.