TreeSet 사용 시 주의할 점 : 정렬 기준에서 동일한 순위를 차지하는 객체는 중복으로 처리된다 !

import java.util.Arrays;
import java.util.TreeSet;

public class P05_CPU스케쥴링복사 {
    public int[] solution(int[][] tasks) {
        int[] answer = new int[tasks.length];
        TreeSet<AllCp> all = new TreeSet<>();

        for (int i=0; i<tasks.length; i++) {
            all.add(new AllCp(i, tasks[i][0], tasks[i][1]));
        }
        System.out.println("tasks.length = " + tasks.length + " / " + "all.size() = "+all.size());
        return answer;
    }

    public static void main(String[] args) {
        P05_CPU스케쥴링복사 T = new P05_CPU스케쥴링복사();
        System.out.println(Arrays.toString(T.solution(new int[][]{{2, 3}, {1, 2}, {8, 2}, {3, 1}, {10, 2}})));
        System.out.println(Arrays.toString(T.solution(new int[][]{{5, 2}, {7, 3}, {1, 3}, {1, 5}, {2, 2}, {1, 1}})));
        System.out.println(Arrays.toString(T.solution(new int[][]{{1, 2}, {2, 3}, {1, 3}, {3, 3}, {8, 2}, {1, 5}, {2, 2}, {1, 1}})));
        System.out.println(Arrays.toString(T.solution(new int[][]{{999, 1000}, {996, 1000}, {998, 1000}, {999, 7}})));
    }
}

class AllCp implements Comparable<AllCp> {
    int num;
    int start;
    int time;
    AllCp(int num, int start, int time) {
        this.num = num;
        this.start = start;
        this.time = time;
    }

    @Override
    public int compareTo(AllCp o) {
        return this.start - o.start;
    }
}

 

위의 코드를 실행시키면 아래와 같은 결과가 나온다.

tasks.length = 5 / all.size() = 5
[0, 0, 0, 0, 0]
tasks.length = 6 / all.size() = 4
[0, 0, 0, 0, 0, 0]
tasks.length = 8 / all.size() = 4
[0, 0, 0, 0, 0, 0, 0, 0]
tasks.length = 4 / all.size() = 3
[0, 0, 0, 0]

 

new AllCp(i, tasks[i][0], tasks[i][1]) 으로 새로운 AllCp 클래스를 만들 때,

동일한 클래스는 없으므로 당연히 TreeSet의 사이즈가 배열의 사이즈와 동일할거라고 생각했었다.

 

하지만 tasks.length = 6 / all.size() = 4 으로 다른 것을 확인하고

이유를 찾아보니 다음과 같았다.

---

TreeSet은 중복된 값을 허용하지 않는 자료구조이며, 정렬 기준에서 동일한 순위를 차지하는 객체는 중복으로 처리된다.

정확히는 compareTo 메서드의 결과가 0인 경우 동일한 순위로 간주되고 중복으로 처리된다.

따라서 만약 두 객체가 compareTo 메서드에서 동일한 값을 반환한다면, TreeSet은 두 객체를 중복으로 간주하고 둘 중 하나만 유지한다. 또한 중복을 허용하지 않기 때문에 새로운 객체를 추가할 때 기존 TreeSet에 이미 동일한 순위의 객체가 있다면 새로운 객체가 추가되지 않는다.

---

TreeSet이 중복을 허용하지 않는다는 것은 알았지만,

중복을 판단하는 기준이 compareTo 메서드의 반환값(동일한 우선순위)인줄은 몰랐어서 문제의 답이 나오지 않던 것이였다 .. !

 

두번째 케이스를 예시로 보면, 아래와 같다.

{5, 2}, {7, 3}, {1, 3}, {1, 5}, {2, 2}, {1, 1}

 

배열의 길이는 6이지만

AllCp 정렬의 기준인 1열의 값이 배열의 3,4,6번째가 1로 동일하므로 중복으로 처리되어 3개가 아닌 1개로 카운팅된다.

 

이제 알았으니 앞으로 알고리즘 문제 풀 때 주의하기 !