java TreeMap과 merge, 공식문서 메서드 시그니처 이해하기

프로그래머스 이중우선순위큐와 백준 7662번을 풀면서 공부한 내용을 정리한다. 저 두 문제는 동일한 문제고, 백준에서는 Python으로 풀었고 프로그래머스에서는 java로 다시 풀었다. 나는 PriorityQueue를 사용해서 풀었는데, 더 나은 방법이 없나...를 찾아보기 위해 java로 제출된 풀이들을 살펴보다보니 TreeMap을 쓴 풀이가 많이 보였다. TreeMap의 경우에는 기존에 개발할 때는 딱히 쓸 일이 없었어서 잘 모르는 자료구조였는데, 이번에 접한 김에 정리해보려고 한다.

TreeMap은 Red Black Tree 기반으로 구현돼있는 자료구조이다.

TreeMap<Integer,String> map1 = new TreeMap<Integer,String>();

이런 방식으로 선언해서 사용할 수 있고, 키와 값이 저장되는 Map형태이다. 여기서 중요한건 자동 정렬이 된다는 점(TreeSet도 자동정렬 되나, Set 형태로 값만 저장되고 중복 저장x)이다. PriorityQueue의 poll해올때 정렬방식에 따라 min/max 값만 받아올 수 있으니까 이중우선순위큐 문제와 같은 상황에서는 maxQueue, minQueue 두개를 따로 따로 만들어줘야된다. 하지만 TreeMap은 하나로 해결할 수 있다! (당연하게도 정렬이 되는거니까..)
TreeMap에서 firstKey()를 가져오면 그것이 min value를 갖고 있는 key이고, lastKey()를 가져오면 그것이 max value를 갖고있는 key이다. (만약에 반대로 하고싶으면 선언할때 Collections.reverseOrder()를 해주면 될듯..)
그래서 이렇게 해서 문제를 해결할 수 있는데, 여기서 추가로 봐야될 메소드가 merge이다.
map을 사용할때는 개수를 저장하는 경우가 많으니, 1)key값이 없으면 1 2)key값이 있으면 기존 value에 +1하기와 같은식으로 값을 입력해야되는 경우가 많다. 이걸 뭐 put으로 당연히 구현할 수는 있지만, 좀 더 빠르게 하는 방법이 merge이다.

int number = 1;
//1
map1.merge(number, 1, Integer::sum);

//2
if (map1.containsKey(number)) {
    map1.put(number, map1.get(number) + 1);
} else {
    map1.put(number, 1);
}

//3
map1.put(number, map1.getOrDefault(number, 1)+1);

위 1, 2,3번 코드는 같은 동작을 수행한다고 보면 된다. merge 메소드에 대해서 공식문서를 찾아보면 다음과 같이 적혀있다.

default V merge(K key,
                V value,
                BiFunction<? super V,? super V,? extends V> remappingFunction)

매번 공식문서 볼때마다 시그니처에 제네릭이 같이 있으면 어떻게 쓰라는건지 헷갈리는데 이 참에 같이 정리하고자 한다. 세 번째 인자를 보면 BiFunction<? super V,? super V,? extends V> remappingFunction이라고 돼있다. BiFunction<~> 형식의 어떤 remappingFunction을 넣으라는 것이다.
? super V는 V의 상위 클래스(list of X or list of superclasses of X can be assigned), ? extends V는 V의 하위클래스(list of X or list of subclasses of X can be assigned)다. 이와 관련해서는 StackOverFlow에 자세한 설명이 있다. 만약 내가 숫자를 넣어준다면 이건 Integer가 되니까 Integer를 넣어준다.
그러면 이제 BiFunction이 무엇인가? 공식문서에는 다음과 같이 나와있다.

Interface BiFunction<T,U,R>
Type Parameters:
T - the type of the first argument to the function
U - the type of the second argument to the function
R - the type of the result of the function
All Known Subinterfaces:
BinaryOperator<T>
Functional Interface:
This is a functional interface and can therefore be used as the assignment target for a lambda expression or method reference.

설명을 보면 Bifunction은 lambda expression((a,b) -> a+b 이런 형식)이나 method reference(Integer::sum 이런 형식)으로 사용될 수 있다. 예시에서 사용했던 게 메서드 참조인데, 이 경우 클래스이름::메서드이름의 형식으로 하게 된다.
BiFunction이 갖고 있는 메서드는 andThen(Function<? super R,? extends V> after)과 apply(T t, U u)인데, merge에서 BiFunction의 역할은 the function to recompute a value if present이다. 그리고 내부 구현을 확인하면 다음과 같다.

private V mergeValue(Entry<K,V> t, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
        V oldValue = t.value;
        V newValue;
        if (t.value == null) {
            newValue = value;
        } else {
            int mc = modCount;
            newValue = remappingFunction.apply(oldValue, value);
            if (mc != modCount) {
                throw new ConcurrentModificationException();
            }
        }
        if (newValue == null) {
            deleteEntry(t);
            return null;
        } else {
            // replace old mapping
            t.value = newValue;
            return newValue;
        }
    }

보면 remappingFunction.apply(oldValue, value)로 동작하고 있는 것을 확인할 수 있다. 그러니까 우리가 merge를 사용할 때 필요한 BiFunction의 메서드는 apply라는 거다.

BiFunction<Integer, Integer, Integer> remappingFunction = new BiFunction<Integer, Integer, Integer>() {
    @Override
    public Integer apply(Integer a, Integer b) {
        return Integer.sum(a, b);
    }
};

최종적으로 이게 우리가 원하는 동작을 하는 BiFunction이다. (더해주는 것) 그런데 이제 BiFunction은 메서드참조나 lambda 형식으로 사용할 수 있다. 따라서 최종적으로

map1.merge(number, 1, (a,b) -> a+b);
map1.merge(number, 1, Integer::sum);

이 두 형식 모두를 사용할 수 있게 된다. 그래서 위와 같이 쓰게 되는 것이다.

이것과 비슷하게 메소드 시그니처만으로는 알기가 어려운 것이, stream().filter()가 있다.

 Stream<T> filter(Predicate<? super T> predicate)

이렇게 돼있는데 Predicate가 뭔지..? 한 번에 알아보기가 어렵다.

Interface Predicate<T>
Type Parameters:
T - the type of the input to the predicate
Functional Interface:
This is a functional interface and can therefore be used as the assignment target for a lambda expression or method reference.

Predicate의 공식문서를 확인해보면 이렇게 돼있다.
이것도 또 lambda나 method reference를 사용할 수 있다고 돼있다. 그러면 BiFunction과 비슷한 느낌으로 쓰면 될 것 같은데, filter()에 적혀있는 설명을 보면 인자로 가져오는 predicate의 역할은 a non-interfering, stateless predicate to apply to each element to determine if it should be included이다. 그러니까 각 원소가 포함될 수 있는지를 결정해주는 것. predicate의 메소드를 확인해보면 and, isEqual, negate, or, test가 있는데 아마 test가 사용될 것 같다. 그래서 내부 구현을 확인해보면 다음과 같다.

public final Stream<P_OUT> filter(Predicate<? super P_OUT> predicate) {
        Objects.requireNonNull(predicate);
        return new StatelessOp<P_OUT, P_OUT>(this, StreamShape.REFERENCE,
                                     StreamOpFlag.NOT_SIZED) {
            @Override
            Sink<P_OUT> opWrapSink(int flags, Sink<P_OUT> sink) {
                return new Sink.ChainedReference<P_OUT, P_OUT>(sink) {
                    @Override
                    public void begin(long size) {
                        downstream.begin(-1);
                    }

                    @Override
                    public void accept(P_OUT u) {
                        if (predicate.test(u))
                            downstream.accept(u);
                    }
                };
            }
        };
    }

역시 test를 사용하고 있다. 만약에, int로 이루어진 배열에서 3 미만인 것만 필터링하고싶다고 가정하자. 그렇다면 우리가 만들고싶은 Predicate는 다음과 같다.

Predicate<Integer> predicate = new Predicate<Integer>(){
	@Override
	public boolean test(Integer num){
		return num<3;
	}
}

이 predicate는 다시 lambda나 method reference를 사용할 수 있으니, 최종적으로 filter()는 다음과 같이 사용할 수 있다.

List<Integer> arr = List.of(1,2,3,4,5);
arr.stream().filter(a->a<3);

method reference를 쓰려면 아마 함수를 따로 생성해줘야할텐데, 그건 패스하겠다.. 어쨌든 이런식으로 공식문서에 있는 시그니처를 보고 사용법을 알아낼 수 있다.