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

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/17677

프로그래머스

코드

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.regex.Pattern;

class Solution {
  public int solution(String str1, String str2) {
	    Map<String,Integer> wordRecord = new HashMap<String,Integer>();
	    Map<String,Integer> wordRecord2 = new HashMap<String,Integer>();
      
		calc(str1, wordRecord);
		calc(str2, wordRecord2);

		if(wordRecord.isEmpty() && wordRecord2.isEmpty() ) return 65536;

		int intersectionCnt = 0 ;
		int unionCnt = 0 ;

		Iterator itr = wordRecord.keySet().iterator();

		while(itr.hasNext()) {

			String key = (String)itr.next();
			int value1 = wordRecord.get(key);
			int value2 = wordRecord2.getOrDefault(key, 0);
			
			if( value2 == 0 ) {
				unionCnt+=value1;
			}else {
				
				int big = value1 > value2 ? value1 : value2  ;
				int small = value1 <= value2 ? value1 : value2 ;
				int minus = big-small;

				if( minus == 0 ) {
					intersectionCnt+=small;
					unionCnt+=small;
				}else{
					intersectionCnt += small;
					unionCnt+=big;
				}
				wordRecord2.remove(key);
			}
		}
      
		Iterator itr2 = wordRecord2.keySet().iterator();

		while(itr2.hasNext()) {
			unionCnt+=wordRecord2.get(itr2.next());
		}		 

		if ( intersectionCnt == 0 ) return 0;

		double result = (double)intersectionCnt/(double)unionCnt;

		return (int)(result * 65536);	
  }
    
  private void calc(String str, Map<String,Integer> records) {		
		for ( int i = 0 ; i < str.length()-1; i++ ) {
			String word = str.substring(i,i+2).toLowerCase();
			boolean check = Pattern.matches("^[a-z]*$", word);

			if(check) {
				records.put(word, records.getOrDefault(word, 0)+1);
			}
		}
	}    
}

제출 결과

나의 풀이

"중복을 허용하는 다중집합"을 처리해야 하는 문제였다...  [ 카카오 풀이 ]

 

먼저 주어진 문자열을 각각 두 글자씩 끊어서 소문자로 변경한 후 알파벳만 가지고 있는 문자들을 Map에 담아주었다.

 

key에는 2글자로 잘린 문자가, value에는 해당 문자가 몇 번 나왔는지를 기록한다.

 

예를 들어 예시에서 st1="aa1+aa2", str2="AAAA12"와 같이 주어진 경우에는

 

wordRecord  = {aa=2} => aa문자가 2번 나온다.
wordRecord2 = {aa=3} => aa문자가 3번 나온다.

 

와 같이 기록된다.

 

st1="aaaaaaaaaaaaaaa", str2="abcabcabc" 와 같은 경우에는

 

wordRecord  =  {aa=14}
wordRecord2 = {ab=3, bc=3, ca=2}

 

와 같이 기록된다.

 

이제 str1문자열이 담긴 wordRecord참조 변수를 기준으로 wordRecord2에 교집합이 존재하는지 확인한다.

 

교집합이 없다면, 해당 문자의 반복횟수만큼(value) 합집합의 갯수를 증가시킨다.

( 처음에 그냥 unionCnt를++해주었는데.. 중복을 허용하는 다중집합이기 때문에 해당 문자가 반복되는 횟수, 즉 value의 값만큼 증가시켜주어야 한다.. )

 

교집합이 있다면, 조건을 비교하게되는데 중복을 허용하는 다중집합의 특징을 보면 아래와 같다.

 

교집합의 개수는 같은 문자열의 갯수 중 작은 값만큼 증가된다.

 

합집합의 갯수는 같은 문자열의 갯수 중 큰 값만큼 증가된다.

 

예를 들어 st1="aa1+aa2", str2="AAAA12"와 같이 주어진 경우에는

 

wordRecord  = {aa=2}
wordRecord2 = {aa=3}

 

wordRecord에는 aa문자열이 2개, wordRecord2에는 aa문자열이 3개 존재한다.

 

이를 아래와 같이 다시 표현해봤을 때..

 

wordRecord = { aa, aa }

wordRecord2 = { aa, aa, aa }

 

두 집합의 교집합은

 

wordRecord의 첫 번째 aa = wordRecord2의 첫번째 aa

wordRecord의 두 번째 aa = wordRecord2의 두번째 aa

 

가 된다. 즉 2가 되고 이 숫자는 해당 문자열의 개수 중 작은 값과 같다.

 

그리고 합집합은 교집합의 갯수 2개 + wordRecord2의 세 번째 aa를 더해서 3이 되고

 

즉, 해당 문자열의 개수 중 큰 값과 같게 된다...

 

그리고 wordRecord2에서는 처리된 문자는 삭제해주면 된다. ( wordRecord를 기준으로 돌기 때문에 2만 삭제해주면 된다. )

 

마지막으로 wordRecord2에 남은 문자는, 교집합에 포함되지 않는 대상을 의미하게 되고 이 문자가 몇 번씩 나오는지 그 value값을 합집합의 개수에 추가시켜주었다.

( 여기서도 처음에 wordRecord2.size()만큼 추가해주었다.. 그러나 이것은 남은 문자열의 개수이지 문자열이 중복되는 개수를 정확하게 세지 못해서 계속 실패하였다.. )

 

처음에 생각하고 의도한 대로 코드를 풀어나갔으나, 중복을 허용하는 합집합의 개수를 count 하는 과정에서 실수를 하여 많은 시간을 뺏어먹었다...ㅠㅠ 실제 시험이었다면 엄청난 멘붕이 왔을 것이다..

 

고민해서 원인을 찾은 만큼.. 실제 코딩 테스트를 보게 될 때는 유연하게 대처할 수 있으면 좋겠다..