java treemap ceilingkey higherkey floorkey lowerkey 를 써 봅시다.

 백준 문제를 풀다 보면, 균형 이진 트리를 써야 하는 경우를 종종 보셨을 겁니다. 이것을 다룰 때, x보다 큰 것 중 제일 작은 키, 같거나 큰 것 중 제일 작은 키, 작은 것 중 제일 큰 키, 작거나 같은 것 중 제일 큰 키를 실시간으로 구해야 하는 상황을 접하셨을 겁니다. java에서는 어떻게 하는지 간단하게 알아봅시다.

 

---

 먼저, c++의 map에는 lower_bound, upper_bound가 있었습니다. 이와 유사하게 자바의 TreeMap에는 ceilingKey와 higherKey가 있습니다. 이 둘의 설명을 보겠습니다.

 

 

 먼저, ceilingKey 메소드는 제일 작은 키를 리턴한다고 하는데요. 조건이 하나 있습니다. given key보다 크거나 같은 것. 예를 들어, 1, 2, 3, 7이 있다고 해 봅시다. 인자로 3이 넘어오면, 3보다 크거나 같은 것은 3과 7이 있어요. 이들 중 제일 작은 건 3이라고 할 수 있어요. 따라서 3을 돌려주게 됩니다. lower_bound와 같습니다.

 

 

 반면에 이것은 이야기가 달라져요. 키가 1, 2, 3, 7인 것이 있고, 인자로 3이 넘어온다면 어떨까요? strictly greater는 <를 의미합니다. 3보다 큰 것 중에서 제일 작은 것을 돌려주므로, 7을 돌려주게 됩니다. 이 두 메서드 모두, 만족하는 키가 없으면 null을 돌려준다는 것을 보시면 됩니다.

 

 대충 key < x인 x의 최솟값을 구한다. 정도로 이해하시면 됩니다. c++에서 upper_bound와 같습니다.

 

 

 인자가 3이 들어왔을 때 파란색은 ceilingKey의 리턴 값이고, 노란색은 higherKey의 리턴 값입니다. 예제를 보겠습니다.

 

 

 예제를 보시면, 15, 2, 3, 1 순서로 TreeMap과 TreeSet에 키를 넣고, 0부터 19까지 돌면서, ceilingKey(i)와 higherKey(i)가 뭔지 출력합니다. TreeSet인 경우도 크게 다르지 않는데요. ceiling은 이상, higher는 초과를 의미합니다.

 

 

 결과는 위와 같습니다. 주목해야 할 점은, 결과가 다른 경우인데요. 3인 경우를 예로 들면, 3 이상인 키 중에서 제일 작은 것은 3이지만, 3 초과인 것 중 제일 작은 것은 15입니다. 따라서, i가 3인 경우에는 ceilingKey의 리턴값이 3이고, higherKey가 15로 다르게 출력됩니다.

 

 다음에 15인 경우를 보시면, 15 이상인 키 값들 중 가장 작은 값은 15입니다만, 15 초과인 키는 없습니다. 따라서 이 때는 15 null이 출력된다는 것도 주의깊게 보시면 되겠습니다.

 

 

---

 그러면, 이하와 미만에 대해서는 어떻게 해야 할까요? iterator로 처리하는 방법이 있을지는 모르겠습니다만, 더 좋은 방법이 있습니다. 바로 floorKey와 lowerKey 메서드를 이용하는 것입니다.

 

 

 먼저 floorKey는 key보다 작거나 같은 것 중에서 제일 큰 키를 리턴합니다. 예를 들어, TreeMap에 1, 2, 3, 7이 있고, key 값으로 3이 들어온다면, 3보다 작거나 같은 키가 1, 2, 3이 있었습니다. 이 중에서 제일 큰 키가 3이므로 3을 돌려줍니다.

 

 

 반면에, lowerKey에 인자 3이 들어오면 이야기가 달라집니다. 1, 2, 3, 7 중에서 3보다 작은 키는 1, 2이고, 이 중 제일 큰 값이 2이므로, 2를 돌려주게 됩니다. x < key인 x의 최대값 정도로 이해하면 좋겠네요.

 

 

 군청색은 key 인자가 3으로 들어왔을 때, floorKey의 리턴 값입니다. 그리고 노란색은 key 인자가 3일 때 lowerKey의 리턴값입니다. 예제를 보겠습니다.

 

 

 다른 건 다 같습니다만, 10번째 줄과 15번째 줄이 다르다는 것만 보시면 됩니다. 각각 i 이하인 최댓값, i 미만인 최댓값을 구합니다.

 

 

 map에 1, 2, 3, 15가 있는 상황이였습니다. key 인자로 1이 넘어왔을 때, 1 이하인 키들 중에 최댓값은 1임을 알 수 있어요. 그런데 1 미만인 키들은 없음을 알 수 있어요. 따라서 null이 리턴됩니다. 3인 경우를 볼까요? 3 이하인 키는 1, 2, 3 3개입니다. 따라서, 3 이하인 키들 중 최대치는 3이 됩니다. 그런데, 3 미만인 것은 1과 2, 2개입니다. 이 중 최대치는 2가 됩니다. 따라서 3일 때 각각 3, 2가 찍히게 됩니다.

 

 당연하게도 제가 이 글에서 소개한 메서드들의 시간 복잡도는 O(log(자료구조에 있는 원소 갯수)) 입니다. 균형 이진 트리이기 때문에, Insert, Delete, Search가 log급으로 떨어지기 때문입니다.