알고리즘(예상 대진표, [1차] 뉴스 클러스터링) - Java

[예상 대진표]

https://programmers.co.kr/learn/courses/30/lessons/12985

프로그래머스

 

* 로직

• (1번, 2번) = 그룹1, (3번, 4번) = 그룹2, (5번, 6번) = 그룹3 등의 패턴을 고려해보면
• 해당 번호 / 2의 값이 곧 속한 그룹의 번호이다. 단, 홀수의 경우 (해당 번호/2 +1)
• 이를 기반으로 로직을 진행한다
  • 두 수 a와 b가 속한 그룹 번호를 구한다
  • 두 수가 속한 그룹이 같은지 판별한다
  • 만약 같지 않다면, 두 수를 각각의 그룹 번호로 갱신하고 이를 반복한다

 

class Solution
{
    public int solution(int n, int a, int b) {
        int answer = 0;

        while (true) {
            answer++;
            int mod_a = a%2 == 0 ? a/2 : (a/2)+1;
            int mod_b = b%2 == 0 ? b/2 : (b/2)+1;

            // 같은 그룹인지 판단
            if(mod_a == mod_b) break;

            // 그룹이 다르다면 -> 반복
            a = mod_a;
            b = mod_b;
        }

        return answer;
    }
}

 

[뉴스 클러스터링]

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

프로그래머스

 

* 로직

• str1과 str2를 모두 소문자로 변환한다
• 이 상태에서 str1과 str2를 조건에 맞게 집합으로 만든다
• 이때, 만들어진 집합을 관리하기 위해 HashMap을 사용한다
• key값은 두 글자씩 끊을 때 만들어지는 단어이고, value값은 리스트 형태이다
• 여기서 리스트는 [해단 key 단어가 str1에서 나온 횟수, 해당 key 단어가 str2에서 나온 횟수] 라고 생각하면 된다
  
  
• 위 과정을 진행하고 나면 HashMap에는 str1과 str2에서 두 글자씩 끊으면서 만들어진 단어(key)가 str1에서 몇 개가 존재하고, str2에서는 몇 개가 나왔는지 정보가 셋팅된다
• 이제 HashMap에서 key를 하나씩 꺼내고
  • 교집합 개수 += Math.min(str1이 가지는 개수, str2가 가지는 개수)
  • 합집합 개수 += Math.max(str1이 가지는 개수, str2가 가지는 개수)
    
    
• 만약 교집합과 합집합이 모두 0이라면 유사도는 1
• 그렇지 않다면, 교집합 / 합집합을 통해 유사도를 구하고 답을 구한다

 

import java.util.ArrayList;
import java.util.HashMap;

class Solution {
    static final double HandleNum = 65536;
    static HashMap<String, ArrayList<Integer>> hashMap;
    
    public int solution(String str1, String str2) {
        int answer = 0;

        // 같은 문자로 통일, 공백 제거
        str1 = str1.toLowerCase();
        str2 = str2.toLowerCase();

        // 다중 배열 생성
        hashMap = new HashMap<>();
        int type = 0;
        makeArr(str1, type);

        type = 1;
        makeArr(str2, type);

        // 교집합과 합집합 확인
        double crossCnt = 0;
        double unionCnt = 0;
        for(String key : hashMap.keySet()) {
            ArrayList<Integer> list = hashMap.get(key);

            crossCnt += Math.min(list.get(0), list.get(1));
            unionCnt += Math.max(list.get(0), list.get(1));
        }

        // 교집합 / 합집합
        double value = 0;
        if(crossCnt==0 && unionCnt == 0) value = HandleNum;
        else value = (crossCnt / unionCnt) * HandleNum;

        answer = (int) Math.floor(value);
        return answer;
    }
    
    private static void makeArr(String str, int type) {
        ArrayList<String> list = new ArrayList<>();
        for(int s=0; s<str.length()-1; ++s) {
            char word1 = str.charAt(s);
            char word2 = str.charAt(s+1);
            int idx1 = word1 - 'a';
            int idx2 = word2 - 'a';
            
            // 둘 중에 공백이면 pass
            if(word1 == ' ' || word2 == ' ') continue;

            // 둘 중에 하나라도 특수기호라면 단어 생성 x
            if(idx1 >= 0 && idx1 <=25 && idx2 >= 0 && idx2 <= 25) {
                String word = Character.toString(word1) + Character.toString(word2);
                list.add(word);

                if(hashMap.containsKey(word)) {
                    ArrayList<Integer> tmp = hashMap.get(word);
                    int cnt = tmp.get(type);
                    tmp.set(type, cnt+1);

                    hashMap.put(word, tmp);
                }

                else {
                    ArrayList<Integer> tmp = new ArrayList<>();
                    for(int i=0; i<2; ++i) {
                        tmp.add(0);
                    }

                    tmp.set(type, 1);
                    hashMap.put(word, tmp);
                }
            }
        }
    }
    
}