프로그래머스 - [1차] 뉴스 클러스터링

프로그래머스 - [1차] 뉴스 클러스터링

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

class Solution {
	public int solution(String str1, String str2) {
		// 대소문자 구분 없게 하기 위함
		str1 = str1.toLowerCase();
		str2 = str2.toLowerCase();
		// 1. str1, 2의 다중 집합
		List<String> multipleSet1 = new ArrayList<>();
		List<String> multipleSet2 = new ArrayList<>();

		// 다중집합 추출용 배열
		char[] str1CharArr = str1.toCharArray();
		for (int i = 0; i < str1CharArr.length - 1; i++) {
			char target1 = str1CharArr[i];
			char target2 = str1CharArr[i + 1];
			if (((target1 >= 'a' && target1 <= 'z'))) {
				if (((target2 >= 'a' && target2 <= 'z'))) {
					String elementSet1 = String.valueOf(target1) + String.valueOf(target2);
					System.out.println("1번 : " + elementSet1);
					multipleSet1.add(elementSet1);
				}
			}
		}
		char[] str2CharArr = str2.toCharArray();
		for (int i = 0; i < str2CharArr.length - 1; i++) {
			char target1 = str2CharArr[i];
			char target2 = str2CharArr[i + 1];
			if (((target1 >= 'a' && target1 <= 'z'))) {
				if (((target2 >= 'a' && target2 <= 'z'))) {
					String elementSet2 = String.valueOf(target1) + String.valueOf(target2);
					System.out.println("2번 : " + elementSet2);
					multipleSet2.add(elementSet2);
				}
			}
		}
		multipleSet1 = multipleSet1.stream().sorted().collect(Collectors.toList());
		multipleSet2 = multipleSet2.stream().sorted().collect(Collectors.toList());

		// 공집합일 경우 유사도 1이기에 바로 리턴
		if(multipleSet1.isEmpty() && multipleSet2.isEmpty()) {
			return 65536;
		}

		List<String> interSectionList = new ArrayList<>();
		int smallStrartIndex = 0;
		if (multipleSet1.size() >= multipleSet2.size()) {
			for (int i = 0; i < multipleSet1.size(); i++) {
				String tmp = multipleSet1.get(i);
				for (int j = smallStrartIndex; j < multipleSet2.size(); j++) {
					String smallTmp = multipleSet2.get(j);
					// 교집합 추가 및 작은쪽 다음꺼 가르키도록
					if (tmp.equals(smallTmp)) {
						interSectionList.add(tmp);
						// 다음꺼부터 검사하면 됨(이미 정렬 해둬서 다음꺼의 교집합은 이 이후부터)
						smallStrartIndex = j+1;
						break;
					}
				}
			}
		} else {
			for (int i = 0; i < multipleSet2.size(); i++) {
				String tmp = multipleSet2.get(i);
				for (int j = smallStrartIndex; j < multipleSet1.size(); j++) {
					String smallTmp = multipleSet1.get(j);
					// 교집합 추가 및 작은쪽 다음꺼 가르키도록
					if (tmp.equals(smallTmp)) {
						interSectionList.add(tmp);
						// 다음꺼부터 검사하면 됨(이미 정렬 해둬서 다음꺼의 교집합은 이 이후부터)
						smallStrartIndex = j+1;
						break;
					}
				}
			}
		}
		// 교집합 개수
		int intersectionSize = interSectionList.size();
		// 교집합이 아닌 원소의 수
		int notIntersectionSet1Count = multipleSet1.size();
		int notIntersectionSet2Count = multipleSet2.size();
		// 교집합 개수만큼 빼주기 -> 중복 해당되는 것들은 교집합 만큼만 삭제됨
		for(String interSection : interSectionList) {
			if(multipleSet1.contains(interSection)){
				notIntersectionSet1Count--;
			}
			if(multipleSet2.contains(interSection)){
				notIntersectionSet2Count--;
			}
		}

		// 3. 자카드 유사도 * 65536 결과를 int로 반환
		return (int)(((double) intersectionSize / (notIntersectionSet2Count + notIntersectionSet1Count + intersectionSize)) * 65536);
	}
}

• str1, str2의 각각 다중집합을 구한다.

  • 조건이 맞으면 다중 집합에 추가한다.
    • 영어로만 이루어짐(대소문자 구분없으니, 최초에 소문자로 초기화)
  • 만일 둘 다 다중 집합이 없다면 유사도 1로 바로 결과 리턴
  • 다중 집합이 존재한다면 정렬알파벳 순으로 정렬한다.
    • 다중 집합은 중복이 가능하니 만일 참조했던 값을 교집합에 포함했는데 동일한 문자열을 추가로 교집합에 추가할 수 있는 것을 방지
      

• 교집합을 순회하며 set1과 set2에 원소 있는지 확인하고 있으면 전체 개수에서 제외시킨다.

  • 교집합에 동일한 String이 여러개 있을 수 있으니 개수만큼 전체 순회
  • 순회하며 포함될 때마다 1씩 제거
  • 이렇게하면 교집합을 제외한 순수한 리스트 개수를 알 수 있음
    • notIntersectionSet1Count, notIntersectionSet2Count

• 계산

  • A Or B : (notIntersectionSet1Count + notIntersectionSet2Count + intersectionSize)
  • A And B : intersectionSize

• 중복 로직을 메서드화

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

class Solution {
    public int solution(String str1, String str2) {
        str1 = str1.toLowerCase();
        str2 = str2.toLowerCase();

        List<String> multipleSet1 = createMultipleSet(str1);
        List<String> multipleSet2 = createMultipleSet(str2);

        if(multipleSet1.isEmpty() && multipleSet2.isEmpty()) {
            return 65536;
        }

        List<String> interSectionList = calculateInterSectionList(multipleSet1, multipleSet2);
        int intersectionSize = interSectionList.size();

        int notIntersectionSet1Count = multipleSet1.size();
        int notIntersectionSet2Count = multipleSet2.size();

        for(String interSection : interSectionList) {
            if(multipleSet1.contains(interSection)){
                notIntersectionSet1Count--;
            }
            if(multipleSet2.contains(interSection)){
                notIntersectionSet2Count--;
            }
        }

        return (int)(((double) intersectionSize / (notIntersectionSet2Count + notIntersectionSet1Count + intersectionSize)) * 65536);
    }

    private List<String> createMultipleSet(String str) {
        List<String> multipleSet = new ArrayList<>();
        char[] charArr = str.toCharArray();

        for (int i = 0; i < charArr.length - 1; i++) {
            char target1 = charArr[i];
            char target2 = charArr[i + 1];
            if (isAlpha(target1) && isAlpha(target2)) {
                String elementSet = String.valueOf(target1) + String.valueOf(target2);
                multipleSet.add(elementSet);
            }
        }

        return multipleSet.stream().sorted().collect(Collectors.toList());
    }

    private boolean isAlpha(char target) {
        return target >= 'a' && target <= 'z';
    }

    private List<String> calculateInterSectionList(List<String> multipleSet1, List<String> multipleSet2) {
        List<String> interSectionList = new ArrayList<>();
        List<String> largeSet;
        List<String> smallSet;

        if (multipleSet1.size() >= multipleSet2.size()) {
            largeSet = multipleSet1;
            smallSet = multipleSet2;
        } else {
            largeSet = multipleSet2;
            smallSet = multipleSet1;
        }

        int smallStartIndex = 0;
        for (int i = 0; i < largeSet.size(); i++) {
            String tmp = largeSet.get(i);
            for (int j = smallStartIndex; j < smallSet.size(); j++) {
                String smallTmp = smallSet.get(j);
                if (tmp.equals(smallTmp)) {
                    interSectionList.add(tmp);
                    smallStartIndex = j+1;
                    break;
                }
            }
        }

        return interSectionList;
    }
}

• 메서드화 하니 보다 깔끔해보이네 ㅎㅎ.. 뤼튼 최고 ㅎ