https://leetcode.com/problems/most-common-word/
Problem
금지된 단어를 제외하고 가장 흔하게 등장하는 단어를 출력하라. 대소문자를 구분하지 않으며, 구두점(마침표,쉼표 등) 또한 무시한다.
또한 소문자로 반환해야한다.
Example
입력
paragraph = "Bob hit a ball, the hit BALL flew far after it was hit.", banned = ["hit"]
출력
"ball"
설명
"hit"는 3번 나오지만 금지 단어이다.
"ball"은 두 번 등장하지만 다른 단어는 등장하지 않으므로 이 문단에서 금지되지 않은 단어 중 가장 빈번한 단어이다.
단락의 단어는 대소문자를 구분하지 않는다.
구두점은 무시된다(예: "ball"과 같은 단어에 인접한 경우에도),
그리고 "hit"는 금지된 단어이기 때문에 더 많이 사용되더라도 정답이 아니다.
전략
전처리 작업 후 개수 처리 및 큰 값 추출
1. 정규식
입력값에는 대소문자가 섞여 있고, 쉼표나 마침표같은 구두점들이 존재한다. 정규식을 이용하면 된다.
처음에는 이러한 정규식으로 replaceAll("[!?',;.]", " ") 구두점들을 모조리 바꾸면 되겠다 생각했는데 추후에 공백과 공백사이에 있는 것도 제거해야하는 등 번거로운 점이 있었다. 따라서 다음과 같이 정규식을 처리하는 게 베스트 이다.
replaceAll("\\W+", " ")
정규식에서 \W는 단어 문자가 아닌 것을 뜻하고 \w은 단어문자를 뜻하니 구별이 필요하다. 그리고 뒤에 +를 붙여서 문자가 아닌 연속적인 값을 " "으로 바꾸는 처리를 함으로써 향후 히든 케이스에서 통과할 수가 있다. 예를들면 "b, ,b" 같은 것도 "b b"로 바꿀 수 있다.
2. 개수 처리
" "으로 분할한 단어들의 개수를 Map을 통해 저장한다.
이때 처음 Map에 등록하는 단어들을 넣을때를 분간하려면 조금 코드가 길어진다. 이를 줄이기 위해 Map 인터페이스에서 제공하는 getOrDefault() 메서드를 사용한다. 이는 값이 존재하지 않는 경우 기본값을 출력하며 존재하는 경우에는 해당하는 값을 출력한다.
Set<String> ban = new HashSet<>(Arrays.asList(banned));
Map<String, Integer> counts = new HashMap<>();
String[] words = paragraph.replaceAll("\\W+", " ").toLowerCase().split(" ");
for (String w : words) {
if (!ban.contains(w)) {
counts.put(w, counts.getOrDefault(w, 0) + 1);
}
}
3. Map에 등록한 개수 중에서 가장 큰 키 찾기
만약 Map.Entry가 무엇인지와 entrySet이 무엇을 반환하는지 잘 모르겠다면 다음 글을 먼저 읽고 오자
https://babgeuleus.tistory.com/118
return Collections.max(counts.entrySet(), Map.Entry.comparingByValue()).getKey();
Collections의 max 메서드를 이용하면 Map에 등록된 Value중 가장 큰 값의 Collection을 반환한다. Collection의 max 메서드의 코드를 보면 다음과 같다.
첫번째 인자로 count Map의 키와 값을 묶은 Set을 넣었고 이들을 Comparator라는 비교 클래스를 사용하기 위해 두번째 인자에는 Map의 내부클래스인 Entry에서 가지고 있는 comparingByValue메서드를 사용한다. 이는 다음과 같다. Map.Entry의 value값을 비교할 때 유용한 메서드 이다.
최종 코드
public class MostCommonWord {
public static void main(String[] args) {
MostCommonWord commonWord = new MostCommonWord();
String result = commonWord.mostCommonWord("Bob hit a ball, the hit BALL flew far after it was hit.",
new String[]{"hit"});
System.out.println(result);
}
public String mostCommonWord(String paragraph, String[] banned) {
Set<String> ban = new HashSet<>(Arrays.asList(banned));
Map<String, Integer> counts = new HashMap<>();
String[] words = paragraph.replaceAll("\\W+", " ").toLowerCase().split(" ");
for (String w : words) {
if (!ban.contains(w)) {
counts.put(w, counts.getOrDefault(w, 0) + 1);
}
}
//return counts.entrySet().stream().max(Map.Entry.comparingByValue()).get().getKey();
return Collections.max(counts.entrySet(), Map.Entry.comparingByValue()).getKey();
}
}
'Algorithm > Leetcode' 카테고리의 다른 글
[Leetcode 234] Palindrome Linked List - 스택,데크,러너 (2) | 2024.01.04 |
---|---|
[Leetcode 42] Trapping Rain Water - 투 포인터 (1) | 2023.12.26 |
[Leetcode 1] Two Sum - 4가지 방식의 풀이 (1) | 2023.12.24 |
[Leetcode 5] Longest Palindromic Substring - 투 포인터+슬라이딩윈도우 (0) | 2023.12.21 |
[Leetcode 937] Reorder Data in Log Files. - 문자열처리 (1) | 2023.12.07 |