프로그래머스 42576: 완주하지 못한 선수

프로그래머스 알고리즘 고득점 kit에 있는 가장 쉬운 해시 문제이다. 이 문제에서 유의해야 할 조건은 동명이인이 있을 수 있다는 것이다. 그래서 일반적인 Set 자료구조를 사용하면 안 되고, Multi Set을 사용해야 하지만 java.util이 기본적으로 제공하지 않는 자료구조이다.

PS를 C++로만 하려다가 Java로 넘어가려 하니 가장 어려운 것이 이런 문제를 해결할 때 성능을 개선하는 것이다. 다양한 방식으로 해결해 보고 성능을 비교해 보겠다.

1. Naive Solution(based on ArrayList)

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        List<String> l = new ArrayList<>(Arrays.asList(participant));
        Collections.sort(l);
        for (String c : completion)
            l.remove(Collections.binarySearch(l, c));
        return l.iterator().next();
    }
}

ArrayList 기반으로 최대한 깎아본 코드이다. 데이터를 정렬하지 않고 무식하게 l.remove(c)로 원소 제거를 수행하면 시간 초과에 걸린다.

사실 데이터가 정렬되어 있든 정렬되어 있지 않든 시간 복잡도는 똑같이 $O(N^2)$이기 때문에 시간 초과에 걸려야 하는데 위 코드는 운이 좋게 통과된 것이라고 볼 수 있다.

실행 시간은 위와 같다.

2. Alternative Solution 1(based on HashMap)

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        HashMap<String, Integer> m = new HashMap<>();
        for (String p : participant)
            m.put(p, m.getOrDefault(p, 0) + 1);
        for (String c : completion)
            m.put(c, m.get(c) - 1);
        for (String k : m.keySet())
            if (m.get(k) != 0)
                return k;
        return "";
    }
}

HashMap을 사용하여 각 원소의 개수를 세고, 다시 빼고, 마지막으로 개수가 1인 원소를 찾아 반환하는 로직이다. 이 코드는 시간 복잡도가 $O(N)$으로 1번 풀이에 비해 비약적인 개선을 이루었다.

실행 시간은 위와 같고, $N$이 $100,000$까지 가능하므로 시간 복잡도가 $O(N^2)$인 풀이는 문제 의도에 부합하지 않는 것이다.

3. Alternative Solution 2(based on ArrayList)

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        ArrayList<String> p = new ArrayList<>(Arrays.asList(participant));
        ArrayList<String> c = new ArrayList<>(Arrays.asList(completion));
        Collections.sort(p);
        Collections.sort(c);
        
        for (int i = 0; i < c.size(); i++)
            if (!p.get(i).equals(c.get(i)))                
                return p.get(i);
        return p.get(p.size() - 1);
    }
}

마지막 해결 방법은 정렬된 ArrayList를 사용한 방법으로, 2번 풀이와 같은 $O(N)$의 시간 복잡도를 갖는다. 이는 participant, completion을 처음부터 순회하며 원소의 불일치가 생기는 지점에서 해당 값을 반환하는 방식이다.

원소 비교 간 equals 메서드를 사용하고 있기 때문에 참가자의 이름 길이도 실행 성능에 영향을 주고 있다. 이는 최대 20자리로 상수로 취급할 수 있지만, 효율성 테스트의 데이터 크기가 그렇게 크지 않아서 2번 풀이에 비해 낮은 효율을 보임을 확인할 수 있다.

Conclusion

결론적으로 해시 문제를 Java로 해결할 땐 HashMap 자료구조를 사용하는 것이 가장 효율적임을 알 수 있었다.

원소 개수를 저장한다는 것 자체가 ArrayList 변수 하나를 사용하는 것보다 메모리 공간을 더 많이 차지하긴 하지만 그렇게 해서 보는 손실보다 실행 효율의 차이로 인한 손실이 더 컸다.

PS만 놓고 보면 Java가 C++보단 훨씬 유연하지 않다. 그러나 그렇기 때문에 C++보다는 효율 개선을 위해 더 많은 걸 생각하게 되어 코드를 짤 땐 더 재미있는 것 같다.