[java 스터디] TreeMap 개념 및 백준 20291번 문제풀이

TreeMap

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

TreeMap에 객체를 저장하면 자동으로 정렬되는데, 키는 저장과 동시에 자동 오름차순으로 정렬된다.

• 숫자(Integer, Double) 타입일 경우에는 값으로 정렬하고
• 문자열(String) 타입일 경우에는 유니코드로 정렬한다.

📌 정렬기준 : 숫자 > 알파벳 대문자 > 알파벳 소문자 > 한글

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

TreeMap은 SortedMap 인터페이스를 구현하고 있어, 데이터를 저장할 때 즉시 정렬하기에 추가나 삭제가 HashMap보다 오래 걸린다. 하지만 정렬된 상태로 Map을 유지해야 하거나 정렬된 데이터를 조회해야 하는 범위 검색이 필요한 경우에는 TreeMap을 사용하는 것이 효율성면에서 좋다.

🤷‍♀️ 그럼 이놈은 어떻게 key를 정렬할 수 있는 것일까?

👉 TreeMap는 내부에 레드-블랙 트리(Red-Black Tree)의 자료구조를 이용하기 때문이다.

Red Black Tree

레드-블랙 트리는 이진탐색트리의 문제점을 보완한 트리이다.

일반적인 이진 탐색 트리는 트리의 높이만큼 시간이 걸린다.
값이 전체 트리에 잘 분산되어 있다면 효율성에 있어 크게 문제가 없으나, 데이터가 들어올 때 값이 한쪽으로 편향되게 들어올 경우, 한쪽 방면으로 크게 치우쳐진 트리가 되어 굉장히 비효율적이게 되버리는 것이다.(기존의 O(logN)의 탐색속도가 최악의 경우 O(N)으로 되버림 => 시간복잡도가 O(N)이라는 것은 이진탐색 트리의 모든 노드를 한번씩 확인해야한다는 말이다.)

레드 블랙 트리는 스스로 균형을 잡는 트리다. 부모 노드보다 작은 값을 가지는 노드는 왼쪽 자식으로, 큰 값을 가지는 노드는 오른쪽 자식으로 배치하여 데이터의 추가나 삭제 시 트리가 한쪽으로 치우쳐지지 않도록 균형을 맞추어준다.(최악의 경우에도 O(logN)으로 나오게 함)

TreeMap 선언

생성하는 명령어는 HashMap과 크게 다르지 않으나 선언 시 크기를 지정해줄 수 없다.

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 값 추가

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

TreeMap은 구조만 HashMap과 다를 뿐 기본적으로 Map 인터페이스를 같이 상속받고 있으므로 기본적인 메소드의 사용법 자체는 HashMap과 동일하다. 입력되는 키 값이 TreeMap 내부에 존재한다면 기존의 값은 새로 입력되는 값으로 대치된다.

TreeMap 단일 값 출력

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구조로 이루어져 있기에 항상 정렬이 되어있어 최소값,최대값을 바로 가져오는 메소드를 지원한다.

✔ firstEntry는 최소 Entry값, firstKey는 최소 Key값,
✔ lastEntry는 최대 Entry값, lastKey는 최대 Key값을 리턴한다.

클래스 상속 구조

아까 TreeMap 은 키값에 따라 오름차순으로 자동정렬된다고 했다.
자동? 👩 그럼 우리는 이것을 내림차순으로 정렬해보고 싶은 욕구가 든다.🤸‍♀️

내림차순으로 정렬하고 싶을때 어떻게 해야할까??

TreeMap 의 클래스 상속 구조를 잠깐 살펴보자.

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable

TreeMap은 HashMap과 동일하게 AbstractMap을 상속받고 있다.
여기서 다른건 TreeMap은 NavigableMap을 implements 받고 있다. NavigableMap은 정렬된 Map에서 여러가지 방법의 탐색을 제공한다.

위와같이 NavigableMap은 오름차순과 내림차순으로 번갈하며 정렬 순서를 바꾸는 descendingMap() 메소드를 제공한다.
이외에도 firstEntry(), lastEntry(), lowerEntry(), higherEntry(), floorEntry(), ceilingEntry() 이 있당

암튼 TreeMap을 내림차순 하고 싶다면 descendingMap() 메서드를 사용하면 된다. 이 메서드는 리턴 값이 NavigableMap이기 때문에 해당 구조로 다시 한번 감싸 주어야 한다.

public class main {

	public static void main(String[] args) {
		TreeMap<Integer, String> tMap = new TreeMap<Integer, String>();
		
		tMap.put(5, "fff");
		tMap.put(3, "bbb");
		tMap.put(2, "ccc");
		tMap.put(7, "ddd");
		tMap.put(1, "aaa");
					
		NavigableMap<Integer, String> desc = tMap.descendingMap();
		Set<Map.Entry<Integer,String>> descS = desc.entrySet();
		for(Map.Entry<Integer,String> entry1 : descS) {
			System.out.println(entry1.getKey() + " " + entry1.getValue());
		}
	}

}

NavigableMap로 감싸준 TreeMap을 하나씩 출력해주기 위해서 entrySet으로 묶은 후 for문으로 하나씩 뽑아 출력해 본다.

7 ddd
5 fff
3 bbb
2 ccc
1 aaa

Comparable

키값에 대한 Compartor 구현으로도 정렬 순서를 바꿀수 있다.
TreeMap의 키는 저장과 동시에 자동 오름차순 정렬된다고 했다.
정렬을 위해 java.lang.Comparable을 구현한 객체를 요구하는데... implements Comparable 하라는 말이다.

💁‍♀️ 우리에게 친숙한 Integer, Double, String은 모두 Comparable 인터페이스를 구현하고 있다.

사용자 정의 클래스도 Comparable을 구현하게 되면 자동 정렬을 할 수 있다.
Comparable에는 compareTo() 가 정의되어 있어서 이 메소드를 사용자 정의 클래스에서 오버라이딩하여 사용할 수 있다.

나이를 기준으로 Person 객체를 오름차순으로 정렬하기 위해 Comparable 인터페이스를 구현한예제를 함 보자.

Person 객체 만들어주고 Comparable 인터페이스를 구현해서 compareTo() 메소드를 재정의해준다.

public class Person implements Comparable<Person> {
    public String name;
    public int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    //compareTo() 메소드 재정의
    public int compareTo(Person o) {
        if (age < o.age) return -1; //나이가 적을 경우는 -1
        else if (age == o.age) return 0; //동일한 경우는 0
        else return 1;// 클 경우는 1을 리턴
    }
}

import java.util.Iterator;
import java.util.TreeSet;

public class ComparableExample {
    public static void main(String[] args) {
        TreeSet<Person> treeSet = new TreeSet<Person>();
        treeSet.add(new Person("김", 45));
        treeSet.add(new Person("이", 25));
        treeSet.add(new Person("최", 31));

        Iterator<Person> iterator = treeSet.iterator();
        while (iterator.hasNext()) {
            Person person = iterator.next();
            System.out.println(person.name + ": " + person.age);
        }
    }
}

👉 결과

이:25
최:31
김:45

 

TreeSet의 객체와 TreeMap의 키가 Comparable을 구현하고 있지 않을 경우, 저장하는 순간 ClassCastException이 발생한다.

🤷‍♀️ 아니 그럼 Comparable 비구현객체는 어떻게 정렬할까?

TreeSet 또는 TreeMap 생성자의 매개값으로 정렬자(Comparator)를 제공하면 Comparable 비구현 객체도 정렬 시킬 수 있다.

TreeMap<K ,V> treeMap = new TreeMap<K, V>(new DescendingComparator() );

Comparable 비구현 과일객체 하나 만들어보자

public class Fruit {
    public String name;
    public int price;

    public Fruit(String name, int price) {
        this.name = name;
        this.price = price;
    }
}

내림차순으로 정렬해주는 정렬자 만들어준다.

import java.util.Comparator;

public class DescendingComparator implements Comparator<Fruit> {
    @Override
    public int compare(Fruit o1, Fruit o2) {
        if (o1.price < o2.price) return 1;
        else if (o1.price == o2.price) return 0;
        else return -1;
    }
}

import java.util.Iterator;
import java.util.TreeSet;

public class ComparatorExample {
    public static void main(String[] args) {
        TreeSet<Fruit> treeSet = new TreeSet<Fruit>(new DescendingComparator());    //내림차순 정렬자 제공
        treeSet.add(new Fruit("포도", 3000));
        treeSet.add(new Fruit("수박", 10000));
        treeSet.add(new Fruit("딸기", 6000));

        Iterator<Fruit> iterator = treeSet.iterator();
        while (iterator.hasNext()) {
            Fruit fruit = iterator.next();
            System.out.println(fruit.name + ": " + fruit.price);
        }
    }
}

결과를 보면 가격을 기준으로 내림차순 된 것을 볼 수 있다.

수박: 10000
딸기: 6000
포도: 3000

 

 

 

- 문제 풀이 

 

백준 20291번 java

 

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        TreeMap<String, Integer> map = new TreeMap<>();
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), ".");
            st.nextToken();
            String extension = st.nextToken();
            map.put(extension, map.getOrDefault(extension, 0) + 1);
        }
        StringBuilder sb = new StringBuilder();
        for (String s : map.keySet()) {
            sb.append(s + " " + map.get(s) + "\n");
        }
        System.out.println(sb);
    }

}