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

Programmers : 뉴스 클러스터링

 

🔗 문제 링크

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

프로그래머스

 

---

💬 문제

이 문제는  문자열 과  정규표현식 에 대한 이해가 있다면 풀 수 있는 문제였다.

 

1. 문자열 str1과 str2가 주어질 때, 각 문자를 두 글자씩 끊어서 다중집합의 원소로 만든다.
   
   - 이때 각 원소는 영문자로만 구성되어 있어야 한다
   
   - 공백이나 숫자, 특수문자가 있는 원소는 제외한다
   
   
2. str1의 집합 A와 str2의 집합 B를 비교하여 교집합과 합집합을 구해준다.
   
   - 원소를 비교해줄 때, 대소문자의 차이는 무시해준다
   
   - 교집합의 크기를 합집합의 크기로 나눈 값(유사도)에 65536을 곱해 출력해준다
   
   - 소수점 아래는 버리고 정수 부분만 출력해준다
   
   - A와 B 모두 공집합일 경우의 유사도는 1이다
   
   

 

728x90

 

---

💡 입출력 예시

4번째 예시를 보면, 문자열 str1에서는 ['aa', 'aa']가 추출되고, str2에서는 ['AA', 'AA', 'AA']가 추출된다. 대소문자의 차이를 무시하므로 교집합은 ['aa', 'aa'], 합집합은 ['aa', 'aa', 'aa']가 된다.

5번째 예시에서는 2개 이상의 영문자로 된 원소가 추출될 수 없으므로 두 집합 모두 공집합이 되므로 유사도는 1이 된다.

 

 

반응형

 

---

🔑 풀이1

• 대소문자의 차이를 없애주기 위해 전부 소문자로 바꿔준다.
  
  
• 두 문자 모두 영문자인 경우만 원소가 될 수 있으므로, 영문자를 제거했을 때 문자의 길이가 0인 경우만 집합에 넣어준다.
  
  
• 집합 A와 B 모두 공집합인 경우에는 유사도가 1이므로, 65536을 곱해 출력해준다.
  
  
• 집합 A와 B의 교집합 크기를 구해준다.
  
  - 집합 A의 요소와 집합 B의 요소가 같은 경우가 교집합 요소가 있는 경우이므로 inter값을 올려준다
  
  - 이미 한 번 비교한 요소를 중복으로 비교해서는 안 되므로, 비교한 집합 B의 요소는 빈 문자열로 바꿔 제거해준다
  
  
• 합집합은 두 집합을 더해 교집합을 빼주면 된다.
  
  
• 교집합의 크기 inter를 합집합의 크기 union으로 나누고 65536을 곱한 다음 정수만 출력해준다.

function solution(str1, str2) {
    str1 = str1.toLowerCase();
    str2 = str2.toLowerCase();
    const A = [];
    const B = [];
    let inter = 0;
    
    // 영문자만 남기기
    for (let i=0; i < str1.length-1; i++) {
        let tmp = str1.substring(i, i+2);
        if (tmp.replace(/[a-z]/g, "").length === 0) {
            A.push(tmp);
        }
    }
    for (let i=0; i < str2.length-1; i++) {
        let tmp = str2.substring(i, i+2);
        if (tmp.replace(/[a-z]/g, "").length === 0) {
            B.push(tmp);
        }
    }
    // 유사도 0
    if (A.length === 0 && B.length === 0) {
        return 65536;
    }
    // 교집합
    for (let i=0; i < A.length; i++) {
        let tmp = A[i];
        
        for (let j=0; j < B.length; j++) {
            if (tmp === B[j]) {
                inter++;
                B[j] = "";  // 중복 검사 방지
                break;
            }
        }
    }
    // 합집합
    const union = A.concat(B).length - inter;
    
    return Math.floor((inter / union) * 65536);
}

 

실행 결과와 채점 결과는 다음과 같다.

 

 

 

---

</> 끊임없이 성장하기 위해 공부한 내용을 글로 작성하고 있습니다. 틀린 부분이나 추가해야 할 부분이 있다면 언제든 댓글로 남겨주세요❗️