(Java) 프로그래머스 뉴스 클러스터링

자카드 유사도를 구하는 문제이다.

예전에는 엄청난 문제 설명에 기가 죽어서 도전해보지 못했지만

이번에는 나름 설계를 먼저 한 후 구현에 도전했다.

// 1. 두글자씩 끊기
// 1-1 소문자열로 통일
// 1-2 공백, 특수문자가 들어간 문자열 버리기
// 2. 교집합과 합집합 구하기
// 3. 자카드유사도 구하기
// 4. 65536을 곱하고 정수부만 출력

 

처음 작성한 코드

package progammers;

import java.util.ArrayList;

public class News_L2 {
    public static void main(String[] args) {
        String str1 = "FRAN C+E";
        String str2 = "french";
        int answer = 0;
        
        // 공백, 특수문자 제거, 소문자열 변환
        str1 = str1.replaceAll("\\W", "").toLowerCase();
        str2 = str2.replaceAll("\\W", "").toLowerCase();

//        String[] list1 = new String[str1.length()-1];
        ArrayList<String> list1 = new ArrayList<>();
        ArrayList<String> list2 = new ArrayList<>();

        // str1 문자열 두 문자씩 끊기
        for (int i = 0; i < str1.length()-1; i++) {
            char ch1 = str1.charAt(i);
            char ch2 = str1.charAt(i+1);
            list1.add(String.valueOf(ch1) + String.valueOf(ch2));
        }

        // str2 문자열 두 문자씩 끊기
        for (int i = 0; i < str2.length()-1; i++) {
            char ch1 = str2.charAt(i);
            char ch2 = str2.charAt(i+1);
            list2.add(String.valueOf(ch1) + String.valueOf(ch2));
        }

        ArrayList<String> g = new ArrayList<>();
        ArrayList<String> h = new ArrayList<>();

        for (int i = 0; i < list1.size(); i++) {
            for (int j = 0; j < list2.size(); j++) {
                if(list1.get(i).equals(list2.get(j))) {
                    g.add(list1.get(i));
                } else {
                    if (!h.contains(list1.get(i))) {
                        h.add(list1.get(i));
                    }
                    if(!h.contains(list2.get(j))) {
                        h.add(list2.get(j));
                    }
                }
            }
        }

        double temp = (double)g.size() / (double)h.size();
        temp = temp * 65536;
        answer = (int)temp;

        System.out.println(answer);

    }
}

 

그러나.... 처음 구현하고 큰 문제점이 두개 있었다.

첫번째는 원소의 중복을 허용한다는 것을 빼먹었고

두번째는 숫자, 공백, 특수문자가 들어간 문자열은 버린다는것을 잘못 이해했다.

문제를 꼼꼼하게 읽지 않아서 숫자는 들어가도 된다고 생각했고

공백과 특수문자는 그냥 지워버리면 된다고 생각했던거다.

aa1+a a2 같은 문자열에서 공백과 특수문자를 지운 aa1aa2 문자열을 만들고

집합을 만들면 된다고 생각했었다.

이렇게 하면 문제가 요구하는 방식이 아니다.

 

한참뒤에 나는 뭔가 잘못되었다는것을 알고 문제를 다시 천천히 읽어보니

완전히 잘못 풀었다는것을 알고 다시 새로 구현했다.

HashMap을 이용해서 중복을 count 하는 방식도 생각해보았지만 기존 방식을 완전히 바꾸고 싶진 않았다.

 

먼저 두글자씩 끊을때 공백과 특수문자가 들어가있다면 그 문자열은 리스트에 저장하지 않고

영문자 문자열만 추가했다.

 

교집합은 list1의 원소를 list2에서 순회하며 공통되는 원소가 있으면 list2에서 제거하고 교집합 리스트에 추가

그리고 합집합에도 추가한다. 공통되는 원소가 없다면 그냥 합집합에 추가한다. 모든 순회가 끝나면

합집합과 list2에 남아있는 원소를 합쳐 최종 합집합을 구한다.

// 1. 두글자씩 끊기
// 1-1 소문자열로 통일
// 1-2 공백, 특수문자가 들어간 문자열 버리기
// 2. 교집합과 합집합 구하기
// 3. 자카드유사도 구하기
// 4. 65536을 곱하고 정수부만 출력

 

최종 코드

import java.util.ArrayList;
class Solution {
    public int solution(String str1, String str2) {
        int answer = 0;
        
        // 소문자열 변환
        str1 = str1.toLowerCase();
        str2 = str2.toLowerCase();
        
        // 두 집합 리스트
        ArrayList<String> list1 = new ArrayList<>();
        ArrayList<String> list2 = new ArrayList<>();
        
        // 공집합과 합집합 리스트
        ArrayList<String> g = new ArrayList<>();
        ArrayList<String> h = new ArrayList<>();
        
        // str1 문자열 두 문자씩 끊고 공백과 특수문자가 들어간 문자열 버리기
        for (int i = 0; i < str1.length()-1; i++) {
            char ch1 = str1.charAt(i);
            char ch2 = str1.charAt(i+1);
            if((ch1 >= 'a' && ch1 <= 'z') && (ch2 >= 'a' && ch2 <= 'z')) {
                list1.add(String.valueOf(ch1) + String.valueOf(ch2));
            }
        }

        // str2 문자열 두 문자씩 끊고 공백과 특수문자가 들어간 문자열 버리기
        for (int i = 0; i < str2.length()-1; i++) {
            char ch1 = str2.charAt(i);
            char ch2 = str2.charAt(i+1);
            if((ch1 >= 'a' && ch1 <= 'z') && (ch2 >= 'a' && ch2 <= 'z')) {
                list2.add(String.valueOf(ch1) + String.valueOf(ch2));
            }
        }

        // 교집합과 합집합
        for(String s : list1) {
            if(list2.remove(s)) {
                g.add(s);
            }
            h.add(s);
        }
        // h와 남아있는 list2 합집합
        h.addAll(list2);
		
        // 자카드 유사도 구하기
        double temp = (double)g.size() / (double)h.size();
        temp = temp * 65536;
        // 합집합이 공집합이면 자카드 유사도가 1이므로
        if(h.size()==0) {
            return 65536;
        }
        answer = (int)temp;
        
        return answer;
    }
}