[프로그래머스][JAVA]Lv. 2 - 뉴스 클러스터링

https://school.programmers.co.kr/learn/courses/30/lessons/17677

프로그래머스

str1과 str2의 교집합과 합집합을 구하여 이를 나누어 유사도를 구하는 문제

• 입력으로는 str1과 str2의 두 문자열이 들어온다. 각 문자열의 길이는 2 이상, 1,000 이하이다.
• 입력으로 들어온 문자열은 두 글자씩 끊어서 다중집합의 원소로 만든다. 이때 영문자로 된 글자 쌍만 유효하고, 기타 공백이나 숫자, 특수 문자가 들어있는 경우는 그 글자 쌍을 버린다. 예를 들어 "ab+"가 입력으로 들어오면, "ab"만 다중집합의 원소로 삼고, "b+"는 버린다.
• 다중집합 원소 사이를 비교할 때, 대문자와 소문자의 차이는 무시한다. "AB"와 "Ab", "ab"는 같은 원소로 취급한다.

str1 = str1.toUpperCase();
str2 = str2.toUpperCase();

먼저 대문자와 소문자 구분을 하지 않기 때문에 그냥 str1과 2를 전부 toUpperCase()로 대문자로 만들어버렸다.

 

String string1 = str1.replaceAll("[^A-Z]", " ");
String string2 = str2.replaceAll("[^A-Z]", " ");
// str1 -> string1, str2 -> string2

그리고 공백, 숫자, 특수 문자의 경우를 처리하기 위해서 replaceAll("[^A-Z]", " ")로 숫자, 특수 문자도 전부 공백으로 만들었다. replaceAll("a", "b")는 string에 "a"를 "b"로 치환해 주는데, 정규식을 이용하여 대문자 A-Z를 제외하면 전부 공백으로 만들어 주었다.

 

public void toKeyword(String st, ArrayList<String> al) {
    for (int i = 0; i < st.length()-1; i++) {
        String str = st.substring(i, i+2);
        if (str.charAt(0) != ' ' && str.charAt(1) != ' ') {
            al.add(str);
        }
    }
}
// string1 -> al1, string2 -> al2

그러고 나서 toKeyword라는 함수를 만들어서 두 글자씩 공백이 아닌 경우에만 ArrayList에 추가하게 하였다.

 

public void toHashMap(ArrayList<String> al, HashMap<String, Integer> hashMap) {
    for (String s : al) {
        if (!hashMap.containsKey(s)) {
            hashMap.put(s, 1);
        } else {
            hashMap.put(s, hashMap.get(s) + 1);
        }
    }
}

대문자와 소문자의 구분을 하지 않게 만들었기 때문에 HashMap을 이용하여 해당 단어의 개수를 저장하였다.

 

for (String s : al1) {
    if (keyword2.containsKey(s) && keyword1.get(s) > keyword2.get(s)) {
        for (int j = 0; j < keyword2.get(s); j++) {
            al3.add(s);
        }
        keyword2.put(s, 0);
    } else if (keyword2.containsKey(s) && keyword1.get(s) <= keyword2.get(s)) {
        for (int j = 0; j < keyword1.get(s); j++) {
            al3.add(s);
        }
        keyword1.put(s, 0);
    }
}

교집합을 구하려고 al1을 탐색하면서 keyword2 HashMap에 key(al1.get(i))가 존재하면서 둘중 더 값이 작은 쪽을 선택하여 al3에 개수만큼 해당 값을 추가해 준다.

 

al4.addAll(al1);
al4.addAll(al2);

for (String s : al3) {
    al4.remove(s);
}

다음 합집합을 구하려고 al4에 al1과 al2의 값들을 전부 추가하고 중복되는 부분(교집합)을 제거해 준다.

 

float ans = (float) al3.size() / al4.size();
if (Float.isNaN(ans)) ans = 1;
ans = ans * 65536;
answer = (int) ans;

return answer;

정답을 구하기 위해서 al3의 size()와 al4의 size()를 나누고 65536을 곱한 다음 int 형으로 바꾸어주고 정답을 출력한다.

str1과 str2가 전부 공백, 특수문자 등 al3.size() / al4.size()가 0 / 0이 되는 경우가 있기 때문에

Float.isNaN()을 이용하여 그 경우 1로 바꾸어 주었다.

 

뭔가 더 줄일 수 있을 것 같지만...

끝!

import java.util.ArrayList;
import java.util.HashMap;

class Solution {
    public int solution(String str1, String str2) {
        int answer = 0;
        
        str1 = str1.toUpperCase();
        str2 = str2.toUpperCase();
        String string1 = str1.replaceAll("[^A-Z]", " ");
        String string2 = str2.replaceAll("[^A-Z]", " ");

        ArrayList<String> al1 = new ArrayList<>();
        ArrayList<String> al2 = new ArrayList<>();
        ArrayList<String> al3 = new ArrayList<>();
        ArrayList<String> al4 = new ArrayList<>();
        HashMap<String, Integer> keyword1 = new HashMap<>();
        HashMap<String, Integer> keyword2 = new HashMap<>();

        toKeyword(string1, al1);
        toKeyword(string2, al2);

        toHashMap(al1, keyword1);
        toHashMap(al2, keyword2);

        for (String s : al1) {
            if (keyword2.containsKey(s) && keyword1.get(s) > keyword2.get(s)) {
                for (int j = 0; j < keyword2.get(s); j++) {
                    al3.add(s);
                }
                keyword2.put(s, 0);
            } else if (keyword2.containsKey(s) && keyword1.get(s) <= keyword2.get(s)) {
                for (int j = 0; j < keyword1.get(s); j++) {
                    al3.add(s);
                }
                keyword1.put(s, 0);
            }
        }
        
        al4.addAll(al1);
        al4.addAll(al2);
        
        for (String s : al3) {
            al4.remove(s);
        }

        float ans = (float) al3.size() / al4.size();
        if (Float.isNaN(ans)) ans = 1;
        ans = ans * 65536;
        answer = (int) ans;

        return answer;
    }

    public void toKeyword(String st, ArrayList<String> al) {
        for (int i = 0; i < st.length()-1; i++) {
            String str = st.substring(i, i+2);
            if (str.charAt(0) != ' ' && str.charAt(1) != ' ') {
                al.add(str);
            }
        }
    }

    public void toHashMap(ArrayList<String> al, HashMap<String, Integer> hashMap) {
        for (String s : al) {
            if (!hashMap.containsKey(s)) {
                hashMap.put(s, 1);
            } else {
                hashMap.put(s, hashMap.get(s) + 1);
            }
        }
    }
}