[LeetCode 819] Most Common Word (Java)

---

풀이

이 문제는 paragraph와 금지 단어들이 문자열 배열 banned로 주어질 때, 금지되지 않은 단어들 중 최빈 단어를 찾는 문제이다.

먼저, paragraph에서 단어들을 추출해야한다.

따라서 split을 해야하는데, paragraph에는 대소문자 뿐만 아니라 쉼표, 구두점, 공백 등이 섞여있기 때문에, 문자열을 쪼개기가 어렵다.

그렇기 때문에 paragraph에서 영문자가 아닌 문자들의 시퀀스를 공백으로 변경해야 한다. 이를 regex로 나타내면 \W+가 된다.

이후 case-insensitive하고 리턴값이 소문자여야하기 때문에, 그냥 toLowerCase를 적용하는 것이 더 편리할 것이다.

이제, paragraph에는 영어 소문자들과 공백만이 존재하므로, split(" ")으로 편하게 단어들을 추출할 수 있다.

다음으로, 단어의 출현 빈도를 세어야한다. 이는 Map으로 세어주면 된다.

이때, 금지된 단어인지 확인해야한다. 하지만, banned를 이용한다면 금지된 단어인지 조회하는 연산은 $O(N)$의 시간복잡도를 가지게 되므로, 비효율적이다.

따라서, 조회 연산의 시간복잡도가 $O(1)$인 해시를 이용하는 것이 합리적이다.

이를 위해, HashSet을 이용하도록 하자.

이제 단어들의 출현 빈도를 모두 세었으면, 최대인 원소를 구한 뒤, 키를 리턴하면 될 것이다.

이를 코드로 옮기면 다음과 같다.

class Solution {
    public String mostCommonWord(String paragraph, String[] banned) {
        String[] words = paragraph.replaceAll("\\W+", " ").toLowerCase().split(" ");
        Set<String> banSet = new HashSet<>(Arrays.asList(banned));
        Map<String, Integer> counts = new HashMap<>();
        for (String word : words) {
            if (!banSet.contains(word))
                counts.put(word, counts.getOrDefault(word, 0) + 1);
        }
        return Collections.max(counts.entrySet(), Map.Entry.comparingByValue()).getKey();
    }
}