자바 SortedSet, TreeSet

Hackerrank에서 자바 과정 연습하던 중에 

문자열과 정수 값 하나를 입력받아 해당 크기의 문자열들을 뽑아내어 정렬해야 하는 문제를 풀게 되었다. 

 

예를 들어,

문자열 javaworld 와 정수 3이 주어진다면

jav, ava, vaw, awo, wor, orl, rld 의 문자열로 파싱 후 이들을 사전 순으로 정렬해야 하는 것 !
결과 : ava, awo, jav, orl, rld, vaw, wor

 

문자열 파싱은 어렵지 않았는데

Arrays 클래스를 임포트 하지 못하는 상황이었어서 정렬이 문제였다.

Discussion을 참조해 sort 메소드를 사용하지 않고 정렬하는 방법을 찾았다. 

 

바로 SortedSet, TreeSet이다. 

 

우선, Set은 중복을 허용하지 않으면서 저장 순서를 유지하는 방식이다. 자바 Collection 중 하나이다. 

Set Collection에서는 HashSet과 TreeSet이 있는데 Set의 사용법은 이전 포스트에서 따로 확인해보자. 

그리고 TreeSet에 대한 내용은 정리를 더 잘해두신 다른 분의 블로그 글을 참고해보자. 

 

그 중 TreeSet은 오늘 배울 SortedSet을 위해 사용된다. 

 

SortedSet

SortedSet은 원소들이 정렬되어 있는 Set이다.

SortedSet 객체 생성 시 원소 정렬을 위해서는

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

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

 

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

따라서 다음과 같이 간단하게 문제를 해결할 수 있다. 

 

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

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

	// Complete the function
	// 'smallest' must be the lexicographically smallest substring of length 'k'
	// 'largest' must be the lexicographically largest substring of length 'k'
	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)의 시간 복잡도를 가진다. 과하다.

 

 

따라서 첫 번째와 마지막에 위치한 문자열을 비교하는 방식이보다 속도가 빠르다. 

이 방식은 비교 및 갱신 연산 O(n) * O(1) 이 2번씩 이뤄지기 때문에 O(n)의 시간 복잡도를 가진다. 

 

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 메소드를 사용하면 된다. 

 

 

TreeSet

* TreeSet에서 정렬을 기능을 하는 메소드를 제공하기도 한다.

- descendingIterator() : 내림차순으로 정렬된 Iterator 반환

- descendingSet() : 내림차순으로 정렬된 NavigableSet 반환

 

* 혹은 범위 검색도 가능하다.

모두 NavigatableSet을 반환하며

inclusive는 해당 객체를 포함할 경우 true, 포함하지 않을 경우 false로 설정해준다. 

 

- headSet(E toElement, boolean inclusive)

 : 기준 객체보다 낮은 객체들을 반환한다. 

- tailSet(E fromElement, boolean inclusive)

 : 기준 객체보다 높은 객체들을 반환한다. 

- subSet(E fromElement, boolean inclusivefrom, E toElement, boolean inclusiveto) 

 : 기준 객체 사이의 객체들을 반환한다. 

 

 

 

 

 

참조 

 

- SorterdSet 사용법 

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

[자바] SortedSet 사용법

- TreeSet의 사용법

http://blog.naver.com/PostView.nhn?blogId=kimstcool01&logNo=220896128159

JAVA) TreeSet의 기본 사용법 / 객체 오름차순, 내림차순 정렬 / 범위 검색