(2018카카오) 뉴스 클러스터링 Java

일반적인 중복이 없는 교집합/합집합 문제였으면 쉽게 풀렸을텐데(HashMap,Set이용)

 

까다로운 조건이 추가되어 애매한 교집합/합집합 문제였다.

 

기획안

/*
        0. 대문자=>소문자로 일괄 변환해버린다.
        1. str 2개씩 쪼개기
        2. 쪼개면서 영문자가 아닌 문자들은 제외.
        3. 쪼갠건 Queue에 넣어놓는다.(x) -> q1,q2로 카운팅으로 대체
        4. 2개의 Map에 key, 중복포함개수(value) 저장
        5. Map의 key에 따라서 중복된 key값이 있으면 value값을 비교.
        => 두 map에 같은 key값이 있는경우, 각 중복원소에따른 value카운트값을 queue에 넣는다.
        7.1 (A+B) - (AnB) = AuB 값
        7.2 (AnB) / (AuB) * 65536 = answer
*/

1. toLowercase()메소드를 이용해서 소문자로 변환한다.

2. charAt을 이용해서 Ascii 코드의 범위를 이용해서 해당 소문자 구간이 아니면 버린다.

 

필자의 코드는 아래와 같다.

import java.util.*;

class Solution {
    int q1=0, q2=0;
    HashMap<String, Integer> map1 = new HashMap<>();//합집합용AUB
    HashMap<String, Integer> map2 = new HashMap<>();//합집합용AUB

    public void fun(String str) {
        for (int i = 0; i < str.length() - 1; i++) {//i+1 오버플로우 안남.
            char front = str.charAt(i);
            char rear = str.charAt(i + 1);

            if (front >= 97 && front <= 122 && rear >= 97 && rear <= 122) {
                String s = front + "" + rear;
                q2++;
                map2.put(s, map2.getOrDefault(s, 0) + 1);
            } else {
                //버려
            }
        }
    }

    public int solution(String str1, String str2) {
        str1 = str1.toLowerCase();
        str2 = str2.toLowerCase();
        Queue<Integer> n = new LinkedList<>();//교집합 각 원소 개수 넣는것
        int mult = 0;
        fun(str1);
        q1=q2;
        q2=0;
        map1=map2;//대입 전달이안돼서,,
        map2=new HashMap<>();//초기화
        fun(str2);

        int answer = 0;
        int plus = q1+ q2;

        for (Map.Entry<String, Integer> entry : map1.entrySet()) {
                int val1 = entry.getValue();
                String s = entry.getKey();
                int val2 = map2.getOrDefault(s,0);
                if(val2==0) continue;
                else{
                    n.offer(val1>val2 ? val2 : val1);//교집합인것중 min
                }
        }
        while(!n.isEmpty()){
            mult+=n.poll();
        }

        if (q1 == 0 && q2 == 0) return 65536;//둘다 공집합인경우 리턴1
        answer = (int) (
                (float)  mult / (plus -mult) * 65536
        );

        return answer;
    }
}

 

 

성능이 더 좋은 다른 코드이다.

 

Java의 패턴(Pattern, Matcher) 정규표현식 활용한 코드이다.

 

정규 표현식	설명
^[0-9]*$	숫자
^[a-zA-Z]*$	영문자
^[가-힣]*$	한글
\\w+@\\w+\\.\\w+(\\.\\w+)?	E-Mail
^\d{2,3}-\d{3,4}-\d{4}$	전화번호
^01(?:0|1|[6-9])-(?:\d{3}|\d{4})-\d{4}$	휴대전화번호
\d{6} \- [1-4]\d{6}	주민등록번호
^\d{3}-\d{2}$	우편번호

 

coding-factory.tistory.com/529

[Java] 자바 정규 표현식 (Pattern, Matcher) 사용법 & 예제

1. 아래의코드에서는 정규식이 " ^[a-z]+$ "이다.

즉, a-z이므로 소문자인경우에만 List에 add한다.

 

2. 여기서도 교집합을 먼저 만드는 방식이다.

교집합의 원소를 하나씩 이중for문으로 찾고, conList(교집합리스트)에 더해주면 나머지 집합에서 remove한다.

import java.util.ArrayList;

class Solution {
  public int solution(String str1, String str2) {
        ArrayList<String> str1List = new ArrayList<>();
        ArrayList<String> str2List = new ArrayList<>();
        ArrayList<String> conList = new ArrayList<>();
        ArrayList<String> finalSumList = new ArrayList<>();

        String tempStr = "";
        for(int i = 0; i < str1.length()-1; i++) {
            tempStr = str1.substring(i, i+2).toLowerCase();
            if(tempStr.matches("^[a-z]+$")) {
                str1List.add(tempStr);
            }
        }

        for(int i = 0; i < str2.length()-1; i++) {
            tempStr = str2.substring(i, i+2).toLowerCase();
            if(tempStr.matches("^[a-z]+$")) {
                str2List.add(tempStr);
            }
        }

        boolean bullshit = false;

        if(str1List.size() == 0 & str2List.size() == 0) {
            bullshit = true;
        }

        //교집합 만들기
        for(int i = 0; i < str1List.size(); i++) {
            for(int j = 0; j < str2List.size(); j++) {
                if(str1List.get(i).equals(str2List.get(j))) {
                    conList.add(str2List.get(j));
                    str1List.remove(i);
                    str2List.remove(j);
                    i--;
                    j = -1;

                    break;
                }
            }
        }

        //합집합 만들기
        finalSumList.addAll(str1List);
        finalSumList.addAll(str2List);
        finalSumList.addAll(conList);



        float zacquard = 1;
        if(bullshit == false) {
            float con = (float) conList.size();
            float sum = (float) finalSumList.size();
            zacquard = (con / sum) * 65536;
        }
        else {
            zacquard = zacquard * 65536;
        }

        int result = (int) zacquard;
        return result;
  }
}