[Programmers] 뉴스 클러스터링

문제

 

2018 KAKAO BLIND RECRUITMENT > [1차] 뉴스 클러스터링

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

 

 

아이디어

 

이번 문제의 아이디어라고 할만한 것은... 딱히 없는 것 같습니다.

 

굳이 선택하자면... 집합 연산에 대해 아는지 정도라고 생각합니다.

 

해당 문제를 풀기에 앞서 집합연산 수식에 대해 알고 가셔야 될 것이 있습니다.

 

n(A∪B) = n(A) + n(B) - n(A∩B)

=> 집합 A와 집합 B의 합집합 개수 = 집합 A의 개수 + 집합 B의 개수 - 집합 A와 집합 B의 교집합 개수

 

 

아마 고등학교 1학년 수학시간에 배우던 수식일 것입니다.

 

해당 식을 이용하여 문제를 푼다면 다음과 같은 절차로 문제를 풀 수 있습니다.

 

• str1의 다중집합 구하기
• str2의 다중집합 구하기
• str1과 str2의 교집합 구하기

 

 

구현 코드 (Java)

 

import java.util.*;

class Solution {
    public int solution(String str1, String str2) {
        List<String> str1List = new ArrayList<String>();
        List<String> str2List = new ArrayList<String>();
        
        // 모두 대문자로 치환
        str1 = str1.toUpperCase();
        str2 = str2.toUpperCase();
        
        for(int i=0; i<str1.length()-1; i++) { // str1탐색하여 다중집합 저장하기
        	char firstChar = str1.charAt(i);
        	char secondChar = str1.charAt(i+1);
        	
        	if(firstChar >= 'A' && firstChar <= 'Z' && secondChar >= 'A' && secondChar <= 'Z') { // 연속된 두 문자가 모두 영어일 경우
        		String str = firstChar + "" + secondChar;
        		str1List.add(str);
        	}
        }
        
        for(int i=0; i<str2.length()-1; i++) { // str2탐색하여 다중집합 저장하기
        	char firstChar = str2.charAt(i);
        	char secondChar = str2.charAt(i+1);
        	
        	if(firstChar >= 'A' && firstChar <= 'Z' && secondChar >= 'A' && secondChar <= 'Z') { // 연속된 두 문자가 모두 영어일 경우
        		String str = firstChar + "" + secondChar;
        		str2List.add(str);
        	}
        }
        
        // A∩B 개수 구하기
        boolean visited[] = new boolean[str2List.size()]; // str2로 만들어진 다중집합의 원소와 같은것이 있었는지 체크
        int intersection = 0; // 교집합 개수
        for(int i=0; i<str1List.size(); i++) {
        	for(int j=0; j<str2List.size(); j++) {
        		if(!visited[j] && str1List.get(i).equals(str2List.get(j))) { // j번째 원소를 사용한 적이 없고 str1의 다중집합과 원소가 같을 경우
        			visited[j] = true;
        			intersection++;
        			break;
        		}
        	}
        }
        
        int union = str1List.size() + str2List.size() - intersection; // n(A∪B) = n(A) + n(B) - n(A∩B)
        
        if(str1List.size() == 0 && str2List.size() == 0) { // 모두 공집합일 경우
        	return 65536*1;
        } else {
        	return 65536*intersection/union;
        }
    }
}

 

 

읽어주셔서 감사합니다.