[LV.1][JAVA] 폰켓몬(feat. TreeSet 알아보기)

https://school.programmers.co.kr/learn/challenges?tab=algorithm_practice_kit

프로그래머스

푸는 동안 사고과정 및 개선점

import java.util.*;

class Solution {
    public int solution(int[] nums) {
        int answer = 0;
        TreeSet<Integer> ts = new TreeSet();
        for(int i: nums){
            ts.add(i); // 일단 이러면 중복제거가 된다
        }
        if(ts.size() >= nums.length/2){
            answer = nums.length/2;
        }else{
            answer = ts.size();
        }
        
        return answer;
    }
}

분류는 Hash다. TreeSet으로 중복제거해서 최대 가지수를 뽑았다.

해시로 분류된 이유는 Set 자료구조를 이용해서 푸는 것 때문일 것으로 추정된다..

---

# 추가 공부

TreeSet 자료구조

import java.util.*;

TreeSet<Integer> ts = new TreeSet<Integer>();
TreeSet<Integer> tsInit = new TreeSet<>(Arrays.asList(1,2,3,3,3));

ts.add(1);
ts.add(2);
ts.add(2);
ts.add(3);
ts.remove(2);
ts.size(); // 크기
ts.clear(); // 전체 날리기

Treeset은 기본으로 레드블랙트리가 적용되어있는 Set 자료구조다. 

https://ko.wikipedia.org/wiki/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99_%ED%8A%B8%EB%A6%AC

레드-블랙 트리 - 위키백과, 우리 모두의 백과사전

레드블랙트리는 부모노드 기준으로 작은게 왼쪽으로, 큰게 오른쪽으로 간다. 그래서 ts.first()는 트리에서 가장 작은 값, ts.last()는 트리에서 가장 큰 값을 출력한다. 오름차순 정렬이 기본이라고 할 수 있다.

그래서 그냥 new 로 만드는게 아니라 Collections.reverseOrder() 해주면 내림차순 정렬이 되는 TreeSet이 생성된다.

TreeSet<Integer> ts = new TreeSet(Comparator.reverseOrder());

Collection인데, Set구조라 순회가 좀 불편하다. Iterator로 감싸서 순회해야된다.

Iterator it = ts.iterator();
while(iter.hasNext()){
    System.out.print(it.next() + "\n");	
}

정렬된 순서대로 iterator가 순회한다.

 

HashSet을 쓰면 요소가 정렬되지않아있지만 해시테이블을 사용해서 O(1)의 속도를 자랑한다. 근데 TreeSet을 쓰면 정렬되어있어서 만약 범위검색 같은 게 필요하면 이걸 써야된다. O(logN)이거나 amortized O(1)이기 때문에 입력이 입력이 엄청 커서 조회에 시간이 막 걸리는 게 아니라면 TreeSet을 써도 될 것 같다.

 

범위검색은 headSet, tailSet을 쓴다. 이게 신세계다.

TreeSet<Integer> numbers = new TreeSet<>();
numbers.add(1);
numbers.add(2);
numbers.add(3);
numbers.add(4);
numbers.add(5);
numbers.add(6);

// headSet() 예시
System.out.println("headSet(4): " + numbers.headSet(4));
System.out.println("headSet(4, true): " + numbers.headSet(4, true));

// tailSet() 예시
System.out.println("tailSet(4): " + numbers.tailSet(4));
System.out.println("tailSet(4, false): " + numbers.tailSet(4, false));

headSet은 주어진 요소보다 작은 범위의 부분집합을 반환한다. 요소를 포함하고 싶으면 true를 같이 넣어주면 된다.

tailSet은 주어진 요소보가 크거나 같은 범위의 부분집합을 반환한다. 그래서 요소가 포함되어있는데, false를 넣어주면 시작 점이 제외된다.

 

도움이 됐다면 댓글이나 공감 버튼 한 번씩 누르고 가주세요!