[프로그래머스] 2018 카카오 블라인드 _ [1차]뉴스 클러스터링

2021_08_08 스터디 문제 풀이

문제 URL : https://programmers.co.kr/learn/courses/30/lessons/17677?language=javascript 

코딩테스트 연습 - [1차] 뉴스 클러스터링

 

문제

 

이번 주는 알고리즘한테 한바가지 맞았다.

우선 위 문제에서 다중집합의 처리가 조금 까다로울 뿐 이외는 구현이 어렵지 않다고 생각을 했고 곧바로 수도코드를 작성해나갔다

 

수도코드

// 1. newStr1, newStr2를 두 글자씩 끊어 집합을 만들어야 함 (두 인자를 모두 소문자화 한다)

// 1-1. 함수 선언 (string을 인자로 받는다) / getStringSet
    // const alphabet = "abcdefghijklmnopqrstuvwxyz"; 알파벳 상수 선언
    // let set = {};
    
    // recursion 재귀함수 선언 (str을 인자로 받음) ex) "france"
        // string의 길이가 1인 경우 재귀함수 끝, 리턴한다

        // string의 앞 두 글자는 str.slice(0, 2); ex) "fr"

        // 만약 앞 두글자가 알파벳에 모두 속한다면 (두 글자 모두 영문)
            // 앞 두 글자를 set객체에 할당
                // set.앞두글자 가 undefined라면, (처음 등장)
                    // set.앞두글자 = 1;
                // 그렇지 않다면
                    // set.앞두글자 = set.앞두글자 + 1; 카운팅 증가
        // return recursion(str.slice(1)); ex) "rance"
    
    // set를 리턴한다


// 2. newStr1, newStr2 상수를 선언, getStringSet에 소문자화한 string 값을 넣고 할당한다 (집합 구하기)

// 3. 합집합 구하기
    // 집합A에도 있고, 집합B에도 있는 경우 각 집합에서의 등장 횟수가 제일 높은 것 
    // 일단 두 집합의 키들을 모두 뽑아서 allSet에 할당, 중복된 값은 넣지 않는다

    // const unionSet = [...allSet];
    
    // allSet을 순회한다
    // 특정 글자a에 대해 최댓값은 A.a와 B.a 중 큰 값만큼 배열에 추가 되어야 함
        // A.a나 B.a가 undefined라면, 1개의 집합에서만 1회 등장한 글자임 / 추가할 필요 없음
        //  A.a와 B.a가 모두 truthy하다면, 
            // const max = Math.max(A.a, B.a); 최대 등장 횟수를 구한다
            // 만약, max가 1이 아니라면, while문으로 unionSet에 특정 글자를 추가한다
            //  let i = 1;
            // while 문은 i가 max 이하일때까지만 동작, 글자 a를 unionSet에 넣어준다

// 4. 교집합 구하기
    // intersection 빈배열 선언

    // A와 B집합 중 Object.keys()로 더 글자가 많이 담긴 집합을 기준으로 반복문을 수행
        // 집합?[i]가 !?집합[?[i]가 undefined가 아니고, intersection에 아직 포함되어있지 않다면 (교집합)
            // const min = Math.min(집합?[i], !?집합[?[i]);
            // min이 1이라면 intersection배열에 글자를 넣어준다

            // 그렇지 않다면 while문으로 intersection에 특정 글자를 추가한다
            //  let i = 1;
            // while 문은 i가 min 이하일때까지만 동작, 글자 a를 intersection에 넣어준다 

// 5. 교집합 / 합집합 * 65536  하고 소수점 아래를 버린 값을 리턴한다

 

풀이

function getStringSet(string) {
    const alphabet = "abcdefghijklmnopqrstuvwxyz"; 
    let set = {};
    
    function recursion(str) {
        if (str.length === 1) return;
        
        const letters = str.slice(0, 2);
        
        if (alphabet.includes(letters[0]) && alphabet.includes(letters[1])) {
            if (set[letters] === undefined) {
                set[letters] = 1;
            } else {
                set[letters] = set[letters] + 1;
            }
        }
        return recursion(str.slice(1));
    }
    recursion(string);
    return set;
}

function solution(str1, str2) {
    const set1 = getStringSet(str1.toLowerCase());
    const set2 = getStringSet(str2.toLowerCase());
    
    const allSet = [];
    Object.keys(set1).forEach((letters) => {
        if (!allSet.includes(letters)) {
            allSet.push(letters);
        }
    })
    Object.keys(set2).forEach((letters) => {
        if (!allSet.includes(letters)) {
            allSet.push(letters);
        }
    })
    const unionSet = [...allSet];
    
    allSet.forEach((letter) => {
        if (set1.letter && set2.letter) {
            const max = Math.max(set1.letter, set2.letter);
            if (max > 1) {
                let i = 1;
                while ( i <= max) {
                    unionSet.push(letter);
                    i++;
                }
            }
        }
    })
    
    const intersectionSet = [];
    const pointSet = Object.keys(set1).length >= Object.keys(set2).length ? set1 : set2 ;
    const otherSet = Object.keys(set1).length >= Object.keys(set2).length ? set2 : set1 ;
    
    const setPointArr = Object.keys(pointSet);

    for (let j = 0; j < setPointArr.length - 1; j++) {
        if (otherSet[setPointArr[j]] && !intersectionSet.includes(setPointArr[j])) {
            const min = Math.min(pointSet[setPointArr[j]], otherSet[setPointArr[j]]);
            if (min === 1) {
                intersectionSet.push(setPointArr[j])
            } else {
                let i = 1;
                while (i < min) {
                    intersectionSet.push(setPointArr[j]);
                    i++;
                }
            }
        }
    }
    let result = intersectionSet.length / unionSet.length * 65536;
    return Number(result.toFixed(0));
}

각 string 값으로 집합을 만들기 위해 getStringSet 함수에서 내부 재귀함수를 호출하여 집합들을 객체 형식으로 키와 카운팅 값을 넣은 뒤 반환하여 받는 코드로 구현했다.

이후에는 합집합을 구하고 교집합을 구하는 로직이다.

호기롭게 수도코드를 1시간 가량 작성하고 코드를 썼는데 

대체...

시간이 부족해서 못풀어 냈다. 다시 한 번 로직을 체크하고 풀어봐야겠다. 

시간 복잡도 O(2n^) 코드로 구현했다