LeetCode 819: 가장 흔한 단어 — 캐리 로직을 이용한 간단한 설명 (Java)

Source: Dev.to

문제 설명

문자열 paragraph와 금지된 단어들의 문자열 배열 banned가 주어졌을 때, 금지되지 않은 가장 빈번한 단어를 반환한다.
반드시 하나 이상의 금지되지 않은 단어가 존재하고, 답은 유일함이 보장된다.

• 단어는 대소문자를 구분하지 않으며, 답은 소문자로 반환한다.
• 구두점은 단어의 일부가 아니다.

간단한 설명

1. paragraph에서 구두점(. 및 기타 비문자) 을 제거한다.
2. 모든 문자를 소문자로 변환한다.
3. banned에 등장하는 단어는 모두 제외한다.
4. 남은 단어들 중 가장 많이 등장하는 단어를 반환한다.

주의할 실수

• . 혹은 ,와 같은 구두점을 제거하지 않는 경우.
• 단어 뒤에 구두점만 있는 "a."와 같은 경계 경우.

예시 1

입력

paragraph = "Bob hit a ball, the hit BALL flew far after it was hit."
banned = ["hit"]

출력

ball

설명

• "hit"은 3번 등장하지만 금지된 단어이다.
• "ball"은 두 번 등장하며, 다른 금지되지 않은 단어보다 많이 등장한다.
• 알고리즘은 대소문자와 구두점을 무시한다.

예시 2

입력

paragraph = "a."
banned = []

출력

a

핵심 아이디어

HashMap을 사용하여 각 금지되지 않은 단어의 등장 횟수를 세고, HashSet을 사용해 금지 단어를 O(1) 시간에 조회한다.

알고리즘

1. 문단 정규화

   • 모든 비문자 문자를 공백으로 바꾸고 소문자로 변환한다.
   • 결과 문자열을 공백 기준으로 분리해 단어 배열을 만든다.

2. 데이터 구조 준비

   • 모든 금지 단어(소문자)를 HashSet에 삽입한다.
   • 단어 개수를 저장할 빈 HashMap을 만든다.

3. 단어 세기

   • 단어 배열을 순회한다.
   • 단어가 금지 집합에 없으면, 맵에서 카운트를 업데이트한다.
   • 가장 높은 카운트를 가진 단어(maxWord)와 그 카운트(max)를 추적한다.

4. maxWord 반환.

간단히 말한 알고리즘

1. 문단을 정리하고, 문자만 남겨서 모두 소문자로 만든 뒤 단어로 나눈다.
2. 금지 단어를 HashSet에 저장해 빠르게 확인한다.
3. 단어 리스트를 훑으며
   • 금지 단어이면 건너뛴다.
   • 그렇지 않으면 HashMap에서 카운트를 증가시킨다.
   • 현재까지 가장 큰 카운트와 해당 단어를 업데이트한다.
4. 루프가 끝난 뒤 저장된 maxWord가 정답이다.

Java 코드

class Solution {
    public String mostCommonWord(String paragraph, String[] banned) {
        // 1. Normalize paragraph
        paragraph = paragraph.toLowerCase().replaceAll("[^a-z]", " ");
        String[] words = paragraph.split("\\s+");

        // 2. Data structures
        Map countMap = new HashMap<>();
        Set bannedSet = new HashSet<>();
        for (String b : banned) {
            bannedSet.add(b.toLowerCase());
        }

        // 3. Count words
        int max = -1;
        String maxWord = "";
        for (String word : words) {
            if (!bannedSet.contains(word) && !word.isEmpty()) {
                int newCount = countMap.getOrDefault(word, 0) + 1;
                countMap.put(word, newCount);
                if (newCount > max) {
                    max = newCount;
                    maxWord = word;
                }
            }
        }

        // 4. Return result
        return maxWord;
    }
}

시간 및 공간 복잡도

• 시간 복잡도: O(n + m) 여기서 n은 paragraph의 문자 수, m은 금지 단어 수이다.
• 공간 복잡도: O(n + m) 단어 카운트를 위한 해시맵과 금지 단어를 위한 해시셋을 위한 공간이다.