[leetCode - Java/Hash] 819. Most Common Word

1. 문제

---

• 문자열 paragraph 배열과 banned 배열이 주어진다. paragraph 배열의 단어는 특수문자를 제외하며 대소문자를 구분하지 않는다. banned 배열의 단어를 제외하고 가장 많이 나오는 단어를 구하여라

2. 의사 코드

---

1. 주어진 paragraph 배열의 특수문자와 공백을 제거해 소문자로 변경
    String[] arr = paragraph.toLowerCase().split(" ");

2. 단어별로 몇번이 나오는지 count하기
    String키값 : Integer벨류값을 갖고있는 HashMap
    for(int i=0; arr배열 길이만큼) {
        map에 arr[i]이 없다면 map에 벨류값1로 저장.
        map에 arr[i]가 있다면 현재 arr[i]의 벨류값에 +1하여 저장
    }

3. key값(단어)과 value(몇번 나왔는지count)값을 저장한 map에 banned배열의 단어가 있는지 확인하여 그 단어를 제외하고 count가 큰 key값 반환
    HashSet<String> set = new HashSet<>(Arrays.asList(banned));    // 중복을 제외하고 set에 banned 요소 저장
      int maxCount = 0; // map의 가장 큰 값 저장

      Entry 타입의 반복문을 통해 키값과 value값 탐색

3. 시도

---

class Solution {
    public String mostCommonWord(String paragraph, String[] banned) {
        String result = "";
        String[] arr = paragraph.toLowerCase().split(" ");

        for(int i=0; i<arr.length; i++) {
            arr[i] = arr[i].replaceAll("[^a-zA-Z0-9]", "");
        }

        HashMap<String, Integer> map = new HashMap<>();
        int max = 0;

        for(int i=0; i<arr.length; i++) {            
            if(!map.containsKey(arr[i])) {
                map.put(arr[i], 1);
            } else {
                int cnt = map.get(arr[i]);
                map.put(arr[i], cnt + 1);    
            }
        }

        HashSet<String> set = new HashSet<>(Arrays.asList(banned));
        int maxCnt = 0;

        for(Map.Entry<String, Integer> entry : map.entrySet()) {
            if(!set.contains(entry.getKey()) && entry.getValue() > maxCnt) {
                result = entry.getKey();
                maxCnt = entry.getValue();
            }
        }

        return result;
    }
}

대부분의 case는 통과했지만 b가 많은 횟수로 나와야하는 case에서 c가 나왔다.

4. 개선

---

split(" ") 과정에서 b와 b사이엔 공백이 없기에 b의 count가 생략된 것이라고 예상된다.

그리고 한번 더 for문에서 정규표현식을 통해 숫자, 영문자 이외의 문자를 제외하는 과정에서 시간복잡도도 같이 올라갈 것으로 예상된다.

    String[] arr = paragraph.toLowerCase().split(" ");

    for(int i=0; i<arr.length; i++) {
        arr[i] = arr[i].replaceAll("[^a-zA-Z0-9]", "");
    }

\W+는 공백이 아닌 문자를 1개 이상 반복하는 패턴으로, 위의 코드를 수정한 최종 코드는 아래와 같다.

class Solution {
    public String mostCommonWord(String paragraph, String[] banned) {
        String result = "";
        String[] arr = paragraph.toLowerCase().split("\\W+");

        HashMap<String, Integer> map = new HashMap<>();
        int max = 0;

        for(int i=0; i<arr.length; i++) {            
            if(!map.containsKey(arr[i])) {
                map.put(arr[i], 1);
            } else {
                int cnt = map.get(arr[i]);
                map.put(arr[i], cnt + 1);    
            }
        }

        HashSet<String> set = new HashSet<>(Arrays.asList(banned));
        int maxCnt = 0;

        for(Map.Entry<String, Integer> entry : map.entrySet()) {
            if(!set.contains(entry.getKey()) && entry.getValue() > maxCnt) {
                result = entry.getKey();
                maxCnt = entry.getValue();
            }
        }

        return result;
    }
}