java lowerkey floorkey ceilingkey higherkey는 키의 순서가 정해진 자료구조에서 쓸 수 있는 유용한 메서드입니다. 이 넷에 대해 이 글에서 간략하게 알아보겠습니다.
navigableMap
먼저, 이들을 알기 위해서는 NavigableMap에 대해 볼 필요가 있어요.
먼저, NavigableMap을 봅시다. 이 클래스는 key ordering이 되어 있다는 전제하에 동작합니다. 순서가 정해졌다. 키의 순서가 정해졌다. 정렬은 특정한 기준으로 순서를 정하는 것이라 할 수 있어요. 이것과 관련있는 것 중 하나가 TreeMap이 있습니다. 이 인터페이스에 있는 메서드 중에는 아래 4개가 있습니다.
- lowerKey
- floorKey
- ceilingKey
- higherKey
이 인터페이스를 구현한 것 중 하나가 TreeMap입니다.
즉, 위에 설명한 4개의 메소드를 TreeMap에서 쓸 수 있다는 이야기가 됩니다. java 에서는 TreeMap이 c++에서 map과 유사하니 알아두시면 좋습니다. 자. 그러면 키의 순서에 대해 알아봅시다. 정수 1, 3, 2, 7, 4 이렇게 5개가 있습니다. 오름차순으로 정렬한다 해 볼게요.
그러면 키가 이 순서대로 배열될 거에요. 즉, 아래와 같은 사실을 알 수 있습니다.
- 키 1 다음에는 2가 옵니다.
- 키 2 다음에는 3이 옵니다.
- 키 3 다음에는 4가 옵니다.
- 키 4 다음에는 7이 옵니다.
어떤 기준으로 된 것인가요? 정수의 크기가 작은 순서대로 배열된 것입니다. key order는 대략 이런 개념이라고 생각하시면 편하겠습니다. greater than, less than는 무엇을 의미할까요? key의 순서와 연관지어서 생각해 보면 쉽습니다. key 3을 기준으로 생각해 봅시다.
less than은 target key 보다 먼저 배치된 키들을 의미합니다. target이 3이라면, 회색으로 표시된 1과 2가 less than key 3이라고 할 수 있어요. greater than은 less than과 반대입니다. 즉, 상대적으로 나중에 배치된 키들을 의미합니다. 아래 그림과 같겠네요.
4와 5는 키 3보다 greater than 이라고 할 수 있어요. 오름차순으로 정렬된 정수의 경우 3보다는 4, 5가 뒤에 오기 때문이에요.
java lowerKey floorKey 메소드
이제 문제의 메서드들을 하나씩 봅시다.
먼저, java lowerKey 메소드입니다. 해당 키보다 strictly less than 이라고 되어 있습니다. 그러면, less than입니다. 이 키들 중 제일 greatest 한 것을 뽑습니다. 무슨 이야기인지 하나씩 볼게요. target을 3이라 할게요.
해당 키보다 먼저 나타나는 것은 1, 2입니다. 이 둘 중에서 제일 큰 키는 2입니다. 따라서, 2를 뽑게 됩니다. 즉, lowerKey는 해당 키보다 먼저 나오는 키들 중, 가장 나중에 나오는 것을 뽑습니다. 위 상황에서는 2를 뽑습니다. 미만인 키 중 제일 큰 것을 뽑는다고 생각하시면 됩니다.
반면 java floorKey는 다릅니다. less than이거나 equal인 키 중 제일 greatest한 것을 뽑습니다. 아까와 같이 target이 3이라고 해 볼게요.
그러면, less than이거나 equal인 것이 1, 2, 3입니다. 이 중 가장 greatest한, 가장 늦게 나오는 키는 3입니다. 따라서, target이 있는 경우에는 target을 뽑게 됩니다. 이하인 키 중 제일 큰 것을 뽑는다고 생각하시면 됩니다.
java ceilingKey higherKey 메서드
이제 이 두 메서드도 보겠습니다.
먼저, ceilingKey는 greater than or equal key 중에, 가장 least한 키를 뽑습니다. 무슨 이야기인가? 그림을 봅시다.
target이 3이라고 해 보겠습니다. 3보다 나중에 나오는 키는 4, 5입니다. 4, 5는 greater than 3 이라고 할 수 있습니다. greater than이거나 equal 이라고 했기 때문에 3, 4, 5들 중에 least key를 뽑게 됩니다. 가장 작다는 것은 가장 먼저 등장하는 것을 의미합니다.
3, 4, 5 중에 가장 먼저 등장하는 것은 3이므로, 3이 됩니다. 이상인 키 중 가장 작은 것을 뽑는다고 생각하시면 되겠습니다.
higherKey 는 어떨까요? strictly greater한 키 중에서, 가장 least한 키를 고릅니다. 무슨 이야기인가? target이 3 이였다고 해 보겠습니다.
이 상황에서 3보다 나중에 나오는 것은 4, 5입니다. 4와 5 중에서 가장 먼저 나오는 것은 4입니다. 따라서, 이 상황에서 target이 3인 경우, higherKey의 리턴값은 4가 됩니다. 초과인 키 중 가장 작은 것을 뽑는다고 생각하시면 되겠습니다. 이제 예제로 들어가 봅시다.
예제로 이해하기
이제 예제 프로그램을 보도록 하겠습니다.
4번째 줄을 보면, TreeMap을 새로 생성하고 있어요. 그런데 생성자의 인자로 reverseOrder를 넘겨주고 있어요. 이것은, 정렬 기준을 역순으로 바꾼다는 것을 의미해요. 저는 key를 아스키 문자로만 이루어진 문자열을 넣었습니다.
String key에 대해서, 원래는 사전순으로 정렬입니다. 그런데, reverse 되었으므로 사전 역순 정렬입니다. 저는, “a”, “b”, “c”, “d” 이렇게 4개를 넣었기 때문에, 상황은 아래와 같이 그려집니다.
이 상황에서 키 b의 lowerKey, floorKey, ceilingKey, higherKey를 구해봅시다. 먼저, lowerKey는 b보다 먼저 등장하는 것 중, 가장 늦게 등장하는 키를 의미해요.
회색으로 표시된 키들 중 가장 늦게 등장하는 키는 ‘c’입니다. 따라서, ‘b’의 lowerKey는 ‘c’라고 할 수 있어요. b의 floorKey는 무엇인가요? b와 같거나 먼저 등장하는 키 중 가장 늦게 등장하는 것을 의미해요. b가 있으니까, 회색 + 군청색 중 가장 늦게 등장한 ‘c’가 답이 되겠네요?
이제 ‘b’의 ceilingKey와 higherKey를 구해 봅시다.
먼저 ceilingKey는 target과 같거나 나중에 등장한 키 중에 가장 먼저 등장하는 키가 답이 됩니다. target이 있기 때문에, b와 a 중에서 가장 먼저 등장하는 키가 답이 되는데요. b가 먼저 등장했습니다. 따라서, b가 답이 됩니다.
higherKey는 strict 하게 target보다 나중에 등장하는 키 중에 가장 먼저 등장하는 키가 답이 됩니다. b보다 나중에 등장한 키는 ‘a’ 하나입니다. 따라서 ‘a’가 답이 됩니다. 예제 1의 출력 결과는 아래와 같습니다.
