알고리즘

프로그래머스JS | [1차] 뉴스 클러스터링

2022. 7. 29. 16:32
목차
  1. ❌ Solution ( 정확성 53.8 / 100 )
  2. ✅ Solution
출처 : 프로그래머스 - 코딩테스트 연습 - 2018 KAKAO BLIND RECRUITMENT- [1차] 뉴스 클러스터링

❌ Solution ( 정확성 53.8 / 100 )

function solution(str1, str2) {
    var answer = 0;
    
    const upperStr1 = str1.toUpperCase();
    const upperStr2 = str2.toUpperCase();
    
    const arrStr1 = splitEl(upperStr1);
    const arrStr2 = splitEl(upperStr2);
    
    const union = [];
    const intersection = [];
    
    
    for(let i = 0; i < arrStr1.length; i++) {
        // 변환된 str1 배열의 인자가 변환된 str2 배열에도 존재하고, 교집합에 들어있지 않다면 교집합에 추가
        if(arrStr2.indexOf(arrStr1[i]) !== -1 && intersection.indexOf(arrStr1[i]) === -1)  {
            intersection.push(arrStr1[i])
        }
        // 합집합 배열에는 변환된 str1 배열을 추가
        if(union.indexOf(arrStr1[i]) === -1) {
            union.push(arrStr1[i]);
        }
        
    }

    for(let j = 0; j < arrStr2.length; j++) {
        // 합집합 배열에 변환된 str2 배열의 인자가 없다면 해당 인자를 합집합 배열에 추가
        if(union.indexOf(arrStr2[j]) === -1) {
            union.push(arrStr2[j])
        }
    }
    
    // 정답 계산식
    answer = parseInt(65536 * (intersection.length / union.length));
    // 두 집합이 공배열일 경우 처리
    if(isNaN(answer)) return 65536;
    return answer;
}

// 문자열을 2글자 단위로 쪼개기 위한 함수
function splitEl(str) {
    const splitedArr = [];
    const reg = /^[A-Z]{2}/g
    
    for(let i = 0; i < str.length -1; i++) {
        const newEl = str.split('')[i] + str.split('')[i+1];
        if(newEl.match(reg) !== null) {
            splitedArr.push(newEl)
        }
    }
    return splitedArr;
}

1. 영문자로 된 글자쌍만 유효하고, 대소문자는 구별하지 않으므로 splitEl 함수를 사용하여 주어진 문자열을 대문자로 통일해준 다음 정규표현식을 사용하여 영문자로 이루어진 다중집합을 return 한다.

2. str1의 다중집합의 원소가 str2의 다중집합에도 들어있고 교집합 배열 intersection 에 포함되어 있지 않다면 해당 원소를 intersection 배열에 추가한다.

3. str1의 다중집합의 원소는 모두 합집합 배열 union 에 추가한다. 

4. str2의 다중집합의 원소 중 union 배열에 들어있지 않은 원소가 있다면 union 배열에 추가한다.

5. 교집합 intersection의 length, 합집합 union 의 length를 사용하여 자카드 유사도를 구하고 65536를 곱한 후에 소수점 아래를 버리고 정수부만 출력한다.

 

💡 자카드 유사도는 원소의 중복을 허용하는 다중집합에 대해 확장할 수 있다. 라는 문구가 있는데, 이를 고려하지 않고 코드를 작성하였다. 

이를 고려한 예제를 확인하면 아래와 같다.

A = { 1, 1, 2, 2, 3 }		// 다중집합 A
B = { 1, 2, 2, 4, 5 }		// 다중집합 B

AnB = { 1, 2, 2 }					// 교집합
AuB = { 1, 1, 2, 2, 3, 4, 5}		// 합집합

교집합의 경우 중복되는 원소의 가장 작은 반복횟수만큼, 합집합의 경우 중복되는 원소의 가장 큰 반복횟수만큼 인자가 들어간다.

✅ Solution

    for (var i = 0; i < arrStr1.length; i++) {
       if (arrStr2.indexOf(arrStr1[i]) >= 0) {
         intersection.push(arrStr2.splice(arrStr2.indexOf(arrStr1[i]), 1))
       }
       union.push(arrStr1[i])
     }

     for (var i = 0; i < arrStr2.length; i++) {
       union.push(arrStr2[i])
     }

첫번째 반복문에서 splice 함수를 사용하여 arrStr2 배열에서 arrStr1 배열과 중복되는 부분을 제거한 다음 두번째 반복문을 사용하여 중복되는 인자가 제거된 arrStr2의 배열을 union 배열에 추가하면 다중집합의 원소중복에 대해서 대응이 가능하다.

'알고리즘' 카테고리의 다른 글

프로그래머스 JS | 올바른 괄호  (0) 2022.11.05
프로그래머스 JS | H-index  (0) 2022.11.05
프로그래머스 JS | 괄호변환  (0) 2022.07.28
백준 JS | 11729번 하노이 탑 이동 순서  (0) 2022.07.07
프로그래머스 JS | 행렬 테두리 회전하기  (0) 2022.07.06
  1. ❌ Solution ( 정확성 53.8 / 100 )
  2. ✅ Solution
'알고리즘' 카테고리의 다른 글
  • 프로그래머스 JS | 올바른 괄호
  • 프로그래머스 JS | H-index
  • 프로그래머스 JS | 괄호변환
  • 백준 JS | 11729번 하노이 탑 이동 순서
3jun
3jun
3jun3jun 님의 블로그입니다.
3jun
3jun
3jun
전체
오늘
어제
  • 분류 전체보기 (94)
    • 프로젝트 (5)
    • Web (9)
    • JavaScript (19)
    • React (12)
    • 알고리즘 (31)
    • Git (3)
    • AWS (3)
    • TypeScript (3)
    • CS (2)
    • Error (6)
    • 회고 (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • msw
  • 백준js
  • Promise
  • 백준 온라인저지
  • state
  • 자바스크립트
  • react
  • 프로그래머스 코딩테스트 js
  • outer environment
  • 프로그래머스 코딩테스트
  • msw 에러
  • 백준 알고리즘
  • 프로그래머스 js
  • 백준 js
  • JavaScript
  • 백준 코테
  • 유효성 로직
  • airbnb style guide
  • this.props.history.push
  • 프로그래머스 코테

최근 댓글

최근 글

hELLO · Designed By 정상우.
3jun
프로그래머스JS | [1차] 뉴스 클러스터링
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.