프로그래머스 뉴스 클러스터링

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

코딩테스트 연습 - [1차] 뉴스 클러스터링

 

제출 날짜: 2021년 9월 21일 화요일

 

 

 

접근 방법

문자열을 소문자로 바꾼 뒤, 알파벳 소문자로 이루어진 경우만 2개씩 쪼개 ArrayList에 넣는다.

이후 ArrayList에서 요소를 제거할 것이기 때문에 우선 두 ArrayList의 size를 더해 합집합이라고 우선 저장한다.

총 2개의 ArrayList를 비교하면서 겹치면 count를 증가시키고 중복되지 않도록 제거한다. 최종 count값이 교집합 개수.

합집합에서 교집합을 빼서 최종 합집합 개수도 구한다. 이때 합집합이 0이라면 65536이 된다.

 

 

 

생각

예제 테스트케이스 4번이 0으로 나와서 풀이를 검색해보니 "모두 공집합일 경우에는 나눗셈이 정의되지 않으므로(division by zero) 따로 J(A,B) = 1로 정의합니다."(https://tech.kakao.com/2017/09/27/kakao-blind-recruitment-round-1/)라고 힌트를 줘서 해결했다. 

제출한 뒤에 다시 틀린 경우가 발생해 검색해보니 중복으로 값을 확인하는 경우(https://programmers.co.kr/questions/19374)가 있었다. 매번 확인한 뒤에 제거하니 문제가 해결되었다.

 

 

 

코드

import java.util.ArrayList;

class Solution {
    public int solution(String str1, String str2) {
        int answer = 0;
        
        ArrayList<String> str1Arr = new ArrayList<>();
        ArrayList<String> str2Arr = new ArrayList<>();
        getTwoWord(str1, str1Arr); // 두 글자씩 끊어서 다중집합(ArrayList)의 원소로 만들기
        getTwoWord(str2, str2Arr);

        int union = str1Arr.size() + str2Arr.size(); // 합집합. 우선 두 집합을 더하기 (이후 중복 제거)
        int intersection = getJSet(str1Arr, str2Arr); // 교집합
        union = union - intersection; // 교집합 빼서 최종 합집합 요소 개수 구하기
        if (union == 0) { // 집합 A와 B가 모두 공집합일 경우에는 나눗셈이 정의되지 않으므로 따로 J(A,B) = 1로 정의
            answer = 65536;
        } else {
            answer = (int) (((double) intersection / union) * 65536); // double 사용해서 0 나오는 것 막기
        }

        return answer;
    }
    
    private static void getTwoWord(String str, ArrayList<String> strArr) { 
    // str를 두 글자씩 끊어 strArr에 넣기
        str = str.toLowerCase(); // 소문자로 바꾸기

        for (int i = 0; i < str.length() - 1; i++) {
            char firstChar = str.charAt(i);
            char secondChar = str.charAt(i + 1);
            if (firstChar >= 97 && firstChar <= 122 && secondChar >= 97 && secondChar <= 122) {
                // 알파벳 소문자로 이루어진 경우만 ArrayList에 넣기
                strArr.add(String.valueOf(firstChar) + String.valueOf(secondChar));
            }
        }
    }

    private static int getJSet(ArrayList<String> str1Arr, ArrayList<String> str2Arr) { 
    // str1Arr와 str2Arr의 교집합 요소 개수 구하기
        int cnt = 0;
        for (int i = 0; i < str1Arr.size(); i++) {
            if (str2Arr.contains(str1Arr.get(i))) { // 해당 원소를 가지고 있다면
                str2Arr.remove(str1Arr.get(i)); // 이후 중복되지 않게 제거하기
                cnt++; // 횟수 세기
            }
        }
        return cnt;
    }
    
}