Skip to content

Latest commit

 

History

History
314 lines (246 loc) · 9.32 KB

220308.md

File metadata and controls

314 lines (246 loc) · 9.32 KB
Raw

Comparator와 Comparable

객체 정렬에 필요한 메소드(정렬기준 제공)를 정의한 인터페이스

  • Comparable : 기본 정렬기준을 구현하는데 사용
  • Comparator : 기본 정렬기준 외에 다른 기준으로 정렬하고자할 때 사용
public interface Comparator {
    int compare(Object o1, Object o2); // o1, o2 두 객체를 비교
    boolean equals(Object obj);        // equals를 오버라이딩할라는 뜻
}
public interface Comparable {
    int compareTo(Object o);           // 주어진 객체(o)를 자신(this)과 비교
}

결과가 양수면 왼쪽이 크고, 0이면 같고, 음수면 오른쪽이 크다.

정렬은 두 대상의 비교와 자리 바꿈을 반복하는 것이다.

compare()와 compareTo()는 두 객체의 비교결과를 반환하도록 작성

public final class Integer extends Number implements Comparable {
    ...
    public in t compareTo(Integer anotherInteger) {
        int v1 = this.value;
        int v2 = anotherInteger.value;
        // 같으면 0, 오른쪽 값이 크면 -1, 작으면 1을 반환
        return (v1 < v2 ? -1 : (v1==v2 ? 0 : 1));
    }
    ...
}
package ch02;

import java.util.*;

public class EX3 {

	public static void main(String[] args) {
		String[] strArr = {"cat", "Dog", "lion", "tiger"};
		
		Arrays.sort(strArr); // String의 Comparable 구현에 의한 정렬
		System.out.println("strArr="+Arrays.toString(strArr));
		
		Arrays.sort(strArr, String.CASE_INSENSITIVE_ORDER); // 대소문자 구분 안함
		System.out.println("strArr="+Arrays.toString(strArr));
		
		Arrays.sort(strArr, new Descending()); // 역순 정렬
		System.out.println("strArr="+Arrays.toString(strArr));
	}
	
}

class Descending implements Comparator {
	public int compare(Object o1, Object o2) {
		if(o1 instanceof Comparable && o2 instanceof Comparable) {
			Comparable c1 = (Comparable)o1;
			Comparable c2 = (Comparable)o2;
			return c1.compareTo(c2) * -1; // -1을 곱해서 기본 정렬방식의 역으로 변경한다.
            // 또는 c2.compareTo(c1)와 같이 순서를 바꿔도 된다.
		}
		return -1;
	}
}

strArr=[Dog, cat, lion, tiger]
strArr=[cat, Dog, lion, tiger]
strArr=[tiger, lion, cat, Dog]

Descending은 새로 정의한 정렬 기준이다.

HashSet

Set

  • HashSet
  • SortedSet
    • TreeSet

HashSet

  • Set인터페이스를 구현한 대표적인 컬렉션 클래스
  • 순서를 유지하려면, LinkedHashSet클래스를 사용

TreeSet

  • 범위 검색과 정렬에 유리한 컬렉션 클래스
  • HashSet보다 데이터 추가, 삭제에 시간이 더 걸림
package ch02;

import java.util.*;

public class EX3 {

	public static void main(String[] args) {
		Object[] objArr = {"1", new Integer(1), "2", "2","3","3","4","4","4"};
		Set set = new HashSet();
		
		for(int i=0; i<objArr.length; i++) {
			set.add(objArr[i]); // HashSet에 objArr의 요소들 저장
		}
		// HashSet에 저장된 요소들 출력
		System.out.println(set);
		
		// HashSet에 저장된 요소들 출력
		Iterator it = set.iterator();
		
		while(it.hasNext()) {
			System.out.println(it.next());
		}
	}
	
}

[1, 1, 2, 3, 4]
1
1
2
3
4

set은 순서가 없어서 정렬을 할 수 없다. 그래서 List로 만들어서 정렬해야 한다.

List list = new LinkedList(set)
Collections.sort(list);

HashSet은 객체를 저장하기 전에 기존에 같은 객체가 있는지 확인해야 한다.
같은 객체가 없으면 저장하고, 있으면 저장하지 않는다.

boolean add(Object o)는 저장할 객체의 equals()와 hashCode()를 호출한다.
그래서 equals()와 hashCode()가 오버라이딩이 되어있어야 한다.

package ch02;

import java.util.*;

public class EX3 {

	public static void main(String[] args) {
		HashSet set = new HashSet();
		
		set.add("abc");
		set.add("abc"); // 중복이라 저장안됨.
		set.add(new Person("David", 10));
		set.add(new Person("David", 10));
		
		System.out.println(set);
	}
	
}

// equals()와 hashCode()를 오버라이딩해야 HashSet이 바르게 동작.
class Person{
	String name;
	int age;
	
	Person(String name, int age){
		this.name = name;
		this.age = age;
	}
	
	public String toString() {
		return name + ":" + age;
	}

	@Override
	public int hashCode() {
		// int hash(Object... values); // 가변인자
		return Objects.hash(name, age);
	}

	@Override
	public boolean equals(Object obj) {
		if (!(obj instanceof Person)) return false;
		
		Person p = (Person)obj;
		// 자신(this)의 이름과 나이를 p와 비교
		return this.name.equals(p.name)&& this.age==p.age; 
	}
}

[David:10, abc]

TreeSet

이진 탐색 트리로 구현. 범위 탐색과 정렬에 유리
이진 트리는 모든 노드가 최대 2개의 하위 노드를 갖음
각 노드가 나무형태로 연결(LinkedList의 변형)

class TreeNode{
    TreeNode left;  // 왼쪽 자식노드
    Object element; // 저장할 객체
    TreeNode right; // 오른쪽 자식노드
}

이진 탐색 트리

부모보다 작은 값은 왼쪽, 큰 값은 오른쪽에 저장
데이터가 많아질 수록 추가, 삭제에 시간이 더 걸린다.(비교 횟수 증가)

TreeSet 데이터 저장과정

boolean add(Object o)를 사용한다.

Ex) TreeSet에 7, 4, 9, 1, 5의 순서로 데이터를 저장하면 아래의 과정을 거친다.
루트부터 트리를 따라 내려가며 값을 비교. 작으면 왼쪽, 크면 오른쪽에 저장한다.

  1. 7을 루트에 저장
  2. 4와 7을 비교, 4를 7의 왼쪽에 저장
  3. 9와 7을 비교, 9를 7의 오른쪽에 저장
  4. 1과 7을 비교, 1과 4를 비교, 1을 4의 왼쪽에 저장
  5. 5와 7을 비교, 4와 5를 비교, 5를 4의 오른쪽에 저장

TreeSet 메소드

생성자 또는 메소드 설명
TreeSet() 기본 생성자
TreeSet(Collection c) 주어진 컬렉션을 저장하는 TreeSet을 생성
TreeSet(Comparator comp) 주어진 정렬기준으로 정렬하는 TreeSet을 생성
Object first() 정렬된 순서에서 첫 번째 객체를 반환
Object last() 정렬된 순서에서 마지막 객체를 반환
Object ceiling(Object o) 지정된 객체와 같은 객체를 반환. 없으면 큰 값을 가진 객체 중 제일 가까운 값의 객체를 반환. 없으면 null
Object floor(Object 0) 지정된 객체와 같은 객체를 반환. 없으면 작은 값을 가진 객체 중 제일 가까운 값의 객체를 반환. 없으면 null
Object higher(Object o) 지정된 객체보다 큰 값을 가진 객체 중 제일 가까운 값의 객체를 반환. 없으면 null
Object lower(Object o) 지정된 객체보다 작은 값을 가진 객체 중 제일 가까운 값의 객체를 반환. 없으면 null
Sorted Set subSet(Object fromElement, Object toElement) 범위 검색의 결과를 반환한다.(toElement는 포함x)
SortedSet headSet(Object toElement) 지정된 객체보다 작은 값의 객체들을 반환한다.
SortedSet tailSet(Object fromElement) 지정된 객체보다 큰 값의 객체들을 반환한다. 
package ch02;

import java.util.*;

public class EX3 {

	public static void main(String[] args) {
		Set set = new TreeSet(); // 범위 검색, 정렬 필요 없음
		for(int i=0; set.size()<6; i++) {
			int num = (int)(Math.random()*45) + 1;
			set.add(num); // set.add(new Integer(num));
		}
		
		System.out.println(set);
	}
	
}

[3, 19, 24, 27, 28, 42]

여기서 TreeSet에 정렬 기준을 주던지, 객체가 정렬 기준을 가지고 있던 해야된다.

TreeSet 범위 검색 - subSet(), headSet(), tailSet()

package ch02;

import java.util.*;

public class EX3 {

	public static void main(String[] args) {
		TreeSet set = new TreeSet();
		
		String from = "b";
		String to = "d";
		
		set.add("abc");			set.add("alien");		set.add("bat");		
		set.add("car");			set.add("Car");			set.add("disc");		
		set.add("dance");		set.add("dZZZZ");		set.add("dzzzz");		
		set.add("elephant");	set.add("elevator");	set.add("fan");		
		set.add("flower");	
		
		System.out.println(set);
		System.out.println("range search : from "+from+" to "+to);
		System.out.println("result1 : "+set.subSet(from,  to));
		System.out.println("result2 : "+set.subSet(from,  "dzzz"));
	}
	
}

[Car, abc, alien, bat, car, dZZZZ, dance, disc, dzzzz, elephant, elevator, fan, flower]
range search : from b to d
result1 : [bat, car]
result2 : [bat, car, dZZZZ, dance, disc]

package ch02;

import java.util.*;

public class EX3 {

	public static void main(String[] args) {
		TreeSet set = new TreeSet();
		int[] score = {80, 95, 50, 35, 45, 65, 10, 100};
		
		for(int i=0; i<score.length; i++) {
			set.add(new Integer(score[i]));
		}
		
		System.out.println("50보다 작은 값 :"+set.headSet(50));
		System.out.println("50보다 큰 값 :"+set.tailSet(50));
		System.out.println("40과 80사이의 값 :"+set.subSet(40,  80));
	}
	
}

50보다 작은 값 :[10, 35, 45]
50보다 큰 값 :[50, 65, 80, 95, 100]
40과 80사이의 값 :[45, 50, 65]

트리 순회

이진 트리의 모든 노드를 한번씩 읽는 것을 트리 순회라고 한다.
부모를 먼저 읽는 것을 전위 순회, 부모를 마지막에 읽는 것이 후위 순회, 왼쪽 자식 - 부모 - 오른쪽 자식 순으로 읽는 것이 중위 순회이다.

레벨 순회는 각 레벨을 좌에서 우로 읽는 것이다.

중위 순회를 하면 오름차순으로 정렬된다.