1. 문제 설명
2. 접근 방식
(1) HashSet
에 나오는 모든 부분 문자열을 저장한다.
(2) map1
, map2
는 HashMap으로서 각 문자열의 문자가 key, 그 문자가 나오는 개수가 value이다.
(3) hashSet에 저장되어 있는 문자를 하나씩 꺼낸다. 해당 문자의 개수를 map1과 map2에서 꺼내서, 합집합과 교집합을 계산한다.합집합
: 둘 중 더 개수가 많은 쪽의 개수를 더한다.교집합
: 둘 중 하나라도 값이 존재하지 않으면 넘어간다. 둘 다 해당 값을 가지고 있다면 개수가 더 적은 쪽의 개수를 더한다.
3. 코드 분석
import java.io.*;
import java.util.*;
class Solution {
public int solution(String str1, String str2) {
HashSet<String> set = new HashSet<>();
HashMap<String, Integer> map1 = new HashMap<>();
HashMap<String, Integer> map2 = new HashMap<>();
split_str(str1, map1, set); split_str(str2, map2, set);
// 2. 교집합, 합집합 구하기
double union = 0;
double inter = 0;
for(String temp : set){
int cnt1 = map1.get(temp) == null ? 0 : map1.get(temp);
int cnt2 = map2.get(temp) == null ? 0 : map2.get(temp);
union += Math.max(cnt1, cnt2);
if(cnt1 == 0 || cnt2 == 0) continue;
else{
inter += Math.min(cnt1,cnt2);
}
}
if(map1.size() == 0 && map2.size() == 0) return 65536;
return (int)((inter/union)*65536) ;
}
// 1. 글자 잘라서 map에 넣기
public void split_str(String str, HashMap<String,Integer> map, HashSet<String> set) {
for(int i = 2; i <= str.length(); i+=1){
boolean isValid = true;
String now = str.substring(i-2, i);
// 97, 122, 65, 90
for(int j = 0; j<2; j++){
if((now.charAt(j)>= 97 && now.charAt(j)<= 122)||
(now.charAt(j)>= 65 && now.charAt(j)<= 90)) continue;
isValid = false;
}
if(isValid) {
set.add(now.toLowerCase());
map.compute(now.toLowerCase(),(key,oldValue) -> oldValue== null? 1 : oldValue+1);
}
}
}
}
4. 성장 하기
다른 사람의 풀이로 공부해보겠다.
class Solution {
// Character.MAX_VALUE는 65535로, 여기에 1을 더한 65536을 MULTIPLIER로 설정
private static final Integer MULTIPLIER = Character.MAX_VALUE + 1;
public int solution(String str1, String str2) {
// 두 입력 문자열을 소문자로 변환
String word1 = str1.toLowerCase();
String word2 = str2.toLowerCase();
// 각 문자열을 부분집합으로 그룹화하여 Map으로 반환
Map<String, Long> words1 = group(word1);
Map<String, Long> words2 = group(word2);
// 두 문자열의 교집합 크기를 계산
Integer intersection = getIntersection(words1, words2);
// 두 문자열의 합집합 크기를 계산
Integer union = getUnion(words1, words2);
// 교집합과 합집합이 모두 0인 경우, MULTIPLIER 반환 (두 문자열이 모두 비어있을 경우)
if (intersection.equals(union) && union.equals(0)) {
return MULTIPLIER;
}
// 교집합 크기를 합집합 크기로 나누고, MULTIPLIER를 곱하여 결과 반환
return (int) (intersection.doubleValue() / union.doubleValue() * MULTIPLIER);
}
// 주어진 문자열에서 2글자씩 끊어 부분집합을 만들고, 각 부분집합의 빈도수를 계산하는 함수
private Map<String, Long> group(String word) {
// 문자열의 길이에서 1을 뺀 범위에서 반복 (마지막 2글자까지 포함하기 위해)
return IntStream.range(0, word.length() - 1)
// 각 인덱스에서 2글자씩 부분 문자열 생성
.mapToObj(index -> word.substring(index, index + 2))
// 생성된 2글자 부분 문자열이 모두 알파벳인지 확인
.filter(text -> text.chars().allMatch(character -> Character.isAlphabetic((char) character)))
// 알파벳 부분 문자열을 Map으로 그룹화, 각 문자열의 빈도를 계산하여 Map으로 반환
.collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
}
// 두 Map에서 공통으로 존재하는 2글자 부분 문자열의 최소 빈도를 합산하여 교집합 크기를 계산하는 함수
private Integer getIntersection(Map<String, Long> words1, Map<String, Long> words2) {
return words1.entrySet().stream()
// words2에도 존재하는 키만 필터링
.filter(entry -> words2.containsKey(entry.getKey()))
// 두 Map에서 공통 키의 빈도 중 최소값을 가져옴
.map(entry -> Math.min(entry.getValue(), words2.get(entry.getKey())))
// 이 최소값들을 합산하여 교집합 크기를 계산
.mapToInt(Long::intValue)
.sum();
}
// 두 Map에서 모든 2글자 부분 문자열의 최대 빈도를 합산하여 합집합 크기를 계산하는 함수
private Integer getUnion(Map<String, Long> words1, Map<String, Long> words2) {
// words2의 복사본을 생성하여, words1의 값을 병합
Map<String, Long> copiedWords = new HashMap<>(words2);
// words1의 각 엔트리에 대해, words2와의 최대 빈도수를 저장
words1.forEach((key, value) -> copiedWords.put(key, Math.max(value, words2.getOrDefault(key, 0L))));
// 모든 값을 합산하여 합집합 크기를 계산
return copiedWords.values().stream()
.mapToInt(Long::intValue)
.sum();
}
}
⛏️Driling
(1)
.filter(text -> text.chars().allMatch(character -> Character.isAlphabetic((char) character)))
용어 | 설명 |
---|---|
text.chars() |
여기서 text 는 문자열이다. 이 문자열을 IntStream() 으로 변환한다.따라서 다음 Stream에서는 text의 문자 하나하나가 int형태로 chaining에 입력 된다. |
.allMatch(n -> predicate(n)) |
Stream의 주어진 모든 요소가 predicate(n)를 만족한다면 true 아니면 false 반환한다. |
Character.isAlphabetic(n) |
n이 알파벳에 해당하면 true, 아니면 false 반환 |
(2)
.collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
용어 | 설명 |
---|---|
Collectors.groupingBy(A,B) |
Stream의 요소들을 첫 번째 인자를 기준으로 그룹화 한다. |
Function.identity() |
Stream에서 주어진 입력을 그대로 반환하는 함수 예를 들어, "ab", "ab", "cd"라는 문자열들이 있다면, "ab"는 두 번, "cd"는 한 번 그룹화 된다. |
Collectors.counting() |
첫 번째 인자로 그룹화 하였을 때, 해당 그룹의 빈도수를 세어서, Map<String, Long> 형태로 반환한다."ab"라는 문자열이 두 번 등장했으면, counting() 은 2를 반환 |
'알고리즘 > 문제 풀이' 카테고리의 다른 글
[백준] 2644 촌수계산 java 풀이 (0) | 2024.08.08 |
---|---|
99클럽 코테 스터디 18일차 TIL + [백준] 5547 일루미네이션 java 완벽 설명! ^^ (0) | 2024.08.08 |
99 클럽 코테 스터디 17일차 TIL + 백준 17834 사자와 토끼 완벽 설명! (0) | 2024.08.07 |
Programmers K진법에서 소수 개수 구하기 java 쉬운 풀이^^ (0) | 2024.08.07 |
[백준] 2667_단지번호 붙이기 java 쉬운 풀이! (0) | 2024.08.06 |