[Java] TreeSet에 중복된 값을 넣어야한다면?

결론부터 말해서..

TreeSet의 중복 요소를 넣고 싶다면

1. Comparable한 객체를 만들어 해당 타입을 갖도록 한다.
2. compareTo를 재정의 할 때 같은 값을 갖는 경우 0이 아닌 다른 값을 리턴하도록 한다.

그런데 중복된 값을 가지는 SortedCollection이 필요하다면 TreeMap을 사용하는 게 더 나아보인다. value를 키로 갖고 중복된 요소의 개수를 value로 갖는 TreeMap을 만들면 위의 1, 2를 굳이 구현할 필요가 없기 때문이다.

 

---

 

작년에 풀었던 이중 우선순위 큐를 다시 풀면서 TreeSet으로 구현하게 되었는데, 몇가지 간과한 부분 때문에 오답처리를 받게 됐다.

해당 특징과 더 나은 방법을 정리해 비슷한 유형에서 같은 실수를 하지 않도록 하자..

 

2023.05.03 - [Algorithm/자료구조] - [Java] 백준 7662 - 이중 우선순위 큐

[Java] 백준 7662 - 이중 우선순위 큐

 

https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/TreeSet.html

TreeSet (Java SE 17 & JDK 17)

 

TreeSet은 Red-Black Tree를 기반으로 만들어진 TreeMap을 기반으로 해서 만들어진 Set이다. 그 덕분에 저장된 요소를 알아서 오름차순 정렬해준다. (물론 인스턴스 생성 시 정렬 기준을 바꾸는 것도 가능하다.)

 

이러한 특성을 이용해서 입력받은 수를 오름차순 정렬할 목적으로 가져다 사용했다. 하지만 오답처리를 받게 됐는데, 입력으로 중복된 요소가 주어지면 오답이 발생한다는 사실을 알았다. 

 

TreeSet도 Set이다.

그렇다. TreeSet은 NavigatableSet의 구현체로 Set의 특성을 갖는다. 즉 중복된 요소를 가질 수 없다는 것이다. 이 특징을 간과해서 중복된 요소가 주어질 때 오답을 받게 된 것이다.

 

시도 1.

기존의 TreeSet은 Integer타입이다. 값이 같아도 다른 요소로 인식하도록 value라는 필드를 갖는 Data클래스를 만들고 해당 타입을 갖는 TreeSet을 만든다. 그리고 compareTo를 오버라이드 해 비교 대상의 value필드를 비교하도록 한다.

결과

여전히 같은 값을 가지는 요소는 2개 이상 가질 수 없었다. 

시도 2.

이유를 곰곰히 생각해보았고 두 비교 대상의 값이 같을 때 0이 아닌 음수나 양수를 리턴하도록 바꿔보았다. 

결과

같은 value를 갖는 Data인스턴스를 포함할 수 있었다.

 

정확한 원리가 궁금해 chatGPT한테 물어보니 TreeSet은 compareTo의 리턴값을 기준으로 노드의 위치를 결정하고 compareTo의 리턴값이 0일 땐 중복된 요소로 간주한다고 한다.