TreeMap [자료구조] ( 프로그래머스 - 전국 대회 선발 고사)

https://school.programmers.co.kr/learn/courses/30/lessons/181851

프로그래머스

 

알고리즘을 풀다보니 프로그래머스 - 전국 대회 선발 고사에서 두개의 값을 쌍으로 저장하면 쉽게 풀릴 수 있다고 생각했다. 

그래서 TreeMap에 대해 좀 더 자세히 알아보고 내것으로 만들려고 찾아보았다.

 

TreeMap 

이진트리를 기반으로한 Map 컬렉션이다.

 

같은 Tree구조로 이루어진 TreeSet과의 차이점은 TreeSet은 그냥 값만 저장한다면, TreeMap은 키와 값이 저장된 Map, Entry를 저장한다는 점이다.

TreeMap에 객체를 저장하면 자동 정렬되는데, 키는 저장과 동시에 자동 오름차순으로 정렬되고 타입이 숫자일 경우 값으로, 문자열일 경우 유니코드로 정렬한다.

정렬 순서는 기본적으로 부모 키값과 비교해서 키값이 낮은 것은 왼쪽 자식 노드에 키 값이 높은 것은 오른쪽 자식 노드에 Map.Entry 객체를 저장한다.

TreeMap은 일반적으로 Map으로써 성능이 HashMap보다 떨어진다.
TreeMap은 데이터를 저장할 때 즉시 정렬하기에 추가나 삭제가 HashMap보다 오래 걸린다.
하지만 정렬된 상태로 Map을 유지해야 하거나 정렬된 데이터를 조회해야 하는 범위 검색이 필요한 경우 TreeMap을 사용하는 것이 효율성면에서 좋다.

 

선언

TreeMap<Integer,String> map1 = new TreeMap<Integer,String>();//TreeMap생성
 
TreeMap<Integer,String> map2 = new TreeMap<>();//new에서 타입 파라미터 생략가능
 
TreeMap<Integer,String> map3 = new TreeMap<>(map1);//map1의 모든 값을 가진 TreeMap생성
 
TreeMap<Integer,String> map6 = new TreeMap<Integer,String>(){{//초기값 설정
    put(1,"a");
}};

추가

TreeMap<Integer,String> map = new TreeMap<Integer,String>();//TreeMap생성
map.put(1, "사과");//값 추가
map.put(2, "복숭아");
map.put(3, "수박");

 

삭제

TreeMap<Integer, String> map = new TreeMap<Integer,String>(){{//초기값 설정
    put(1, "사과");//값 추가
    put(2, "복숭아");
    put(3, "수박");
}};
map.remove(1); //key값 1 제거
map.clear(); //모든 값 제거

출력

TreeMap<Integer,String> map = new TreeMap<Integer,String>(){{//초기값 설정
    put(1, "사과");//값 추가
    put(2, "복숭아");
    put(3, "수박");
}};
		
System.out.println(map); //전체 출력 : {1=사과, 2=복숭아, 3=수박}
System.out.println(map.get(1));//key값 1의 value얻기 : 사과
System.out.println(map.firstEntry());//최소 Entry 출력 : 1=사과
System.out.println(map.firstKey());//최소 Key 출력 : 1
System.out.println(map.lastEntry());//최대 Entry 출력: 3=수박
System.out.println(map.lastKey());//최대 Key 출력 : 3

 

TreeMap을 그냥 print하게 되면 { }로 묶어 Map의 전체 key값, value가 출력된다.
특정 key값의 value를 가져오고 싶다면 get(key)를 사용하면 된다.
TreeMap은 HashMap과 달리 Tree구조로 이루어져 있기에 항상 정렬이 되어있어 최소값,최대값을 바로 가져오는 메소드를 지원한다.

 

TreeMap은 HashMap과 달리 Tree구조로 이루어져 있기에 항상 정렬이 되어있어 최소값,최대값을 바로 가져오는 메소드를 지원한다.
firstEntry는 최소 Entry값, firstKey는 최소 Key값,
lastEntry는 최대 Entry값, lastKey는 최대 Key값을 리턴한다.

 

전체 값 출력

TreeMap<Integer,String> map = new TreeMap<Integer,String>(){{//초기값 설정
    put(1, "사과");//값 추가
    put(2, "복숭아");
    put(3, "수박");
}};
 
//entrySet() 활용
for (Entry<Integer, String> entry : map.entrySet()) {
    System.out.println("[Key]:" + entry.getKey() + " [Value]:" + entry.getValue());
}
//[Key]:1 [Value]:사과
//[Key]:2 [Value]:복숭아
//[Key]:3 [Value]:수박
 
//KeySet() 활용
for(Integer i : map.keySet()){ //저장된 key값 확인
    System.out.println("[Key]:" + i + " [Value]:" + map.get(i));
}
//[Key]:1 [Value]:사과
//[Key]:2 [Value]:복숭아
//[Key]:3 [Value]:수박

 

TreeMap의 전체요소를 출력하려면 HashMap과 마찬가지로 entrySet()이나 keySet() 메소드를 활용한다.

특정 key값의 value를 가져오고 싶다면 get(key)를 사용하면 되고,
전체를 출력하려면 entrySet()이나 keySet()메소드를 활용하여 Map의 객체를 반환받은 후 출력하면 된다.

entrySet()은 key와 value가 모두 필요할 경우 사용하며
keySet()은 key 값만 필요할 경우 사용하는데 key값만 받아서 get(key)를 활용하여 value를 출력할 수도 있다.
하지만, key 값을 이용해 value를 찾는 과정에서 시간이 많이 소모되므로 많은 양의 데이터를 가져와야 한다면 entrySet()이 좋다.
(약 20%~200% 성능 저하가 있다고 한다.)

 

Iterator 사용

 

TreeMap<Integer,String> map = new TreeMap<Integer,String>(){{//초기값 설정
    put(1, "사과");//값 추가
    put(2, "복숭아");
    put(3, "수박");
}};
		
//entrySet().iterator()
Iterator<Entry<Integer, String>> entries = map.entrySet().iterator();
while(entries.hasNext()){
    Map.Entry<Integer, String> entry = entries.next();
    System.out.println("[Key]:" + entry.getKey() + " [Value]:" +  entry.getValue());
}
//[Key]:1 [Value]:사과
//[Key]:2 [Value]:복숭아
//[Key]:3 [Value]:수박
		
//keySet().iterator()
Iterator<Integer> keys = map.keySet().iterator();
while(keys.hasNext()){
    int key = keys.next();
    System.out.println("[Key]:" + key + " [Value]:" +  map.get(key));
}
//[Key]:1 [Value]:사과
//[Key]:2 [Value]:복숭아
//[Key]:3 [Value]:수박

 

 

출처(감사합니다💜) https://coding-factory.tistory.com/557