[LeetCode] 819. Most Common Word

https://leetcode.com/problems/most-common-word/

Most Common Word - LeetCode

banned 목록에 없는 단어 중 가장 많이 반복된 단어 return

String 구현 문제(?)인데, 난 이런 문제는 꼭 Map을 쓰고 싶더라 (아주 제격이다)

class Solution {
    public String mostCommonWord(String paragraph, String[] banned) {
        String wordOnly = paragraph.replaceAll("[^a-zA-Z]"," ");    
        wordOnly = wordOnly.replace("  ", " ").toLowerCase();

        String[] strList = wordOnly.split(" ");
        Map<String, Integer> map = new HashMap<>();
        for(String str : strList){
            map.put(str, map.getOrDefault(str,0)+1);
        }
             
        for(String ban : banned){
        	map.remove(ban);
        }
        
        int max = 0;
        for(String word : map.keySet()){
            max = Math.max(max, map.get(word));
        }

        for(String word : map.keySet()){
            if(map.get(word) == max){
                return word;
            }
        }
        
        return wordOnly.replace(" ", "");
    }
}

---

정규식을 써서 기존의 영문자가 아닌 특수문자를 모두 공백으로 치환하고, 기존 공백에 추가 공백이 생긴 부분을 없애준다. 리턴하는 단어는 모두 소문자여야 하고, 반복횟수도 쉽게 파악하기 위해 소문자로 치환한다.

 

✳영어가 아닌 모든 문자 공백으로 만들기

paragraph.replaceAll("[^a-zA-Z]"," ");  

 

공백으로 모든 단어를 split()하고, 맵에 담는다.

그리고, banned에 포함된 단어라면 맵에서 지운다.

 

이 때, 최대값을 가진 key를 찾아야하므로 int max값을 얻고, 그 다음 max값과 일치하는 key값을 반환한다.

마지막 리턴 값은 단어하나에 특수문자가 들어갈 경우, 공백이 생기니까 공백을 지워준 단어만 return하는 것으로 끝맺었다.

Accepted 13 ms 39.3 MB

 

LeetCode Solution

class Solution {
    public String mostCommonWord(String paragraph, String[] banned) {

        // 1). replace the punctuations with spaces,
        // and put all letters in lower case
        String normalizedStr = paragraph.replaceAll("[^a-zA-Z0-9 ]", " ").toLowerCase();

        // 2). split the string into words
        String[] words = normalizedStr.split("\\s+");

        Set<String> bannedWords = new HashSet();
        for (String word : banned)
            bannedWords.add(word);

        Map<String, Integer> wordCount = new HashMap();
        // 3). count the appearance of each word, excluding the banned words
        for (String word : words) {
            if (!bannedWords.contains(word))
                wordCount.put(word, wordCount.getOrDefault(word, 0) + 1);
        }

        // 4). return the word with the highest frequency
        return Collections.max(wordCount.entrySet(), Map.Entry.comparingByValue()).getKey();
    }
}

>> 

✳ 공백 사이의 단어 split()

1. 단어 사이 공백이 하나일 때 (+없이)

String[] words = normalizedStr.split("\\s");

 

2. 공백 수가 가변적일 경우 (예 : 단어사이에 공백이 두개 있는 것도 정상적으로 단어 단위로 나누고 싶을 때 : +)

String[] words = normalizedStr.split("\\s+");

 

👩‍💻 오호..이렇게 정규식을 잘 활용하면 코드를 잘 줄일 수 있을듯..!

---

처음에 문제 풀 때 map.put() 하기전에 banned에 없는 단어만 add하고 싶은데 조건식을 어떻게 짤까 하다가, 결국 잘 안돼서 그냥 다 넣고, banned에 있는것만 빼주는 걸로 했었는데 솔루션을 보니 HashSet에 담아서 contains() 메서드를 사용한 것을 배울 수 있었다.

내 풀이는 map에 전체 단어를 넣고, ban 단어를 빼는 과정을 해준거고, 솔루션 방법은 Set에 ban 단어를 저장하고 ban이 아닌 단어만 저장한 방식이다.

 

내 풀이 : map에 있는 단어 저장 + ban 단어 탐색 + map에서 단어 제거

솔루션 : ban에 있는 단어 저장 + ban 단어 탐색 +  ban이 아닌 단어 map에 저장

 

리턴 방식도 더 간단하다.

 

Collections.max(), Collections.min() 메서드를 이용해서 원소 내 최대(최소)값을 쉽게 얻을 수 있다.

max(Collection<? extends T> coll, Comparator<? super T> comp)

: Returns the maximum element of the given collection, according to the order induced by the specified comparator.

: comparator의 정렬순서에 따라 Collections의 최대 요소를 리턴한다.

즉, Map.Entry.comparingByValue() 를 이용해 오름차순 정렬된 comparator로 기준을 정하고, 기존에 <단어,반복수>를 저장한 map에서 value값이 최대인 value를 리턴 (.getKey()를 이용해 key값을 리턴한다.)

 

Map.Entry.comparingByValue()

: Returns a comparator that compares Map.Entry in natural order on value.

Map.Entry.comparingByValue().reversed()

 

https://docs.oracle.com/javase/8/docs/api/java/util/Map.Entry.html#comparingByValue--

Map.Entry (Java Platform SE 8 )

 

솔루션으로 풀이한 코드가 런타임이 더 길다.

class Solution {
    public String mostCommonWord(String paragraph, String[] banned) {
        String wordOnly = paragraph.replaceAll("[^a-zA-Z]"," ").toLowerCase();
        String[] strList = wordOnly.split("\\s+");
        
        Set<String> ban = new HashSet<>();
        for(String banWord : banned){
            ban.add(banWord);
        }
        
        Map<String, Integer> map = new HashMap<>();
        for(String str : strList){
            if(!ban.contains(str)){
                 map.put(str, map.getOrDefault(str,0)+1);
            }
        }
        
        return Collections.max(map.entrySet(), Map.Entry.comparingByValue()).getKey();
    }
}

Accepted 18 ms 39.5 MB