[JAVA] Collection - Set (SortedSet, TreeSet)

이전 포스팅에서는 HashSet에 대해 정리해보았다. TreeSet에 대해서는 이전에 코딩테스트 문제를 풀면서 접해본 적이 있다. HashSet을 정렬하는 방법을 찾아보다가 발견했었는데, 오늘 그 자료구조에 대해 드디어 정리를 하게 되었다 ㅎㅎ 

 

TreeSet  / SortedSet

TreeSet은 이진검색트리 구조 (root와 node)이기 때문에 HashSet과는 다르게 추가적인 메소드들이 존재한다.

TreeSet에 대해 얘기해보기 전에, 먼저 SortedSet에 대해 알아봐야할 것 같다. 

SortedSet 인터페이스는 Collection이기도 하며 Set이기도 하다 (Set을 상속한 인터페이스).

SortedSet은 말그대로 원소들이 정렬되어있는 Set이다. SortedSet 객체 생성 시, 원소 정렬을 위해서는

- Comparable 인터페이스를 구현하고 있는 클래스의 객체를 원소로 사용하거나

- Comparator 인터페이스를 구현한 로직을 객체 생성 시 넘겨줘야 한다. 

자바에서 SortedSet 인터페이스의 기본 구현체는 TreeSet 클래스이다. 

 

정렬이 가능하기 때문에, 정렬 기능의 메소드들이 추가적으로 존재한다. 

범위 접근

hadSet(Object) : 기준 객체보다 낮은 객체들을 반환

tailSet(Object) : 기준 객체보다 높은 객체들을 반환

subSet(ObjectA, ObjectB) : 기준 객체 사이 (ObjectA 보다 크거나 같고 ObjectB 보다 작은 원소)를 반환

List<String> animals = Arrays.asList("Dog", "Cat", "Tiger", "Lion", "Elephant");
SortedSet<String> animalSet = new TreeSet<>(animals);
// [Cat, Dog, Elephant, Lion, Tiger]

Set<String> headSet = animalSet.headSet("Elephant"); // [Cat, Dog]
Set<String> tailSet = animalSet.tailSet("Elephant"); // [Elephant, Lion, Tiger]
Set<String> subSet = animalSet.subSet("Dog", "Lion"); // [Dog, Elephant]

가장자리 접근

first() : 가장 작은 인자를 반환 

last() : 가장 큰 인자를 반환 

List<String> animals = Arrays.asList("Dog", "Cat", "Tiger", "Lion", "Elephant");
SortedSet<String> animalSet = new TreeSet<>(animals);
// [Cat, Dog, Elephant, Lion, Tiger]

animals.first(); // Cat
animals.last(); // Tiger

 

 

다음 코드를 보고 SortedSet에 대하여 더 자세히 알아보자.

문자열 s와 substring할 문자열의 길이 k를 변수로 받는 메소드가 있다고 생각해보자.

랜덤하게 주어지는 문자열 s를 k 길이만큼 잘라서 사전식 순서로 정렬할 때,

가장 빨리 나오는 순서인 문자열 'smallest'과 

가장 늦게 나오는 순서인 문자열 'largest'를 구하는 메소드를 구현해보자.  

사전식 순서 (Lexicographic Order)  
1) 대문자가 항상 소문자보다 먼저 온다.
2) 숫자는 항상 문자 앞에 온다.
- ex. A, ABC, Abc, C, a, abc, abcd ...

기본적으로 String 클래스는 Comparator 인터페이스를 구현하고 있기 때문에, 문자열을 정렬하는 SortedSet(TreeSet)을 생성하는 것은 쉽다. 

import java.util.SortedSet;
import java.util.TreeSet;

public static String getSmallestAndLargest(String s, int k) {
	String smallest = "";
	String largest = "";

	int len = s.length() - k + 1;
	SortedSet<String> result = new TreeSet<String>();
	for (int i = 0; i < len; i++) {
		result.add(s.substring(i, i + k)); // 모든 경우의 수 저장 
	}
	smallest = result.first(); 
	largest = result.last();

	return smallest + "\n" + largest;
}

여담이지만 사실 위 답안은 효율적은 답안은 아니다. 

 

이 문제는 첫 번째와 마지막 문자열을 찾기만 하면 된다.

하지만 위의 TreeSet의 경우 '모든 경우의 수를 저장한다'는 것은 O(n) * O(logn)의 시간 복잡도를 가지며, 비효율적이다. 

(빅오 표기법에 대해서는 추후 알아보도록 하자. 공부할 수록 공부할 것이 늘어나는 마법...) 

 

따라서 아래 방법이 더 효율적이다.

public static String getSmallestAndLargest(String s, int k) {
    String smallest = "";
    String largest = "";
        
    int len = s.length() - k + 1;
    smallest = s.substring(0, k);
    largest = s.substring(0, k);
        
    for(int i = 0; i < len; i++){
        String temp = s.substring(i, i + k);
        if(smallest.compareTo(temp) > 0 ) smallest = temp;
        if(largest.compareTo(temp) < 0 ) largest = temp;
    }
        
    return smallest + "\n" + largest;
}

compareTo를 사용한 위 답안은 O(n) * O(1)이 2번씩 이뤄지기 때문에 O(n)의 시간 복잡도를 가진다. 

 

 

 

 

---

[참고]

https://heedipro.tistory.com/241

https://doompok.tistory.com/6

https://www.daleseo.com/java-sorted-set/