[합집합, 교집합, 병합 정렬] 프로그래머스 lv2. 뉴스클러스터링

문제 : 프로그래머스 lv2. 뉴스클러스터링

(바로가기)[https://school.programmers.co.kr/learn/courses/30/lessons/17677]

문제 요구사항

// 1. str1과 str2를 정규식을 사용하여 영문만 남기고 숫자, 특수문자 등은 모두 " " 공백처리한다.
// 2. 문자열 배열을 구한다.
//     영문이 연속으로 나와야 문자열이 유효하다. 따라서 두번째 문자에 " " 공백이 있으면 제외한다.
// 3. 문자열 배열의 합집합을 구한다.
// 4. 문자열 배열의 교집합을 구한다.
// 5. 답을 구한다.

내 풀이

def solution(str1, str2):
    def getJachard(a,b):
        common=[]
        for each in a:
            if each in b:
                b.remove(each)
                common.append(each)
        return round(len(common)/(len(a)+len(b)),7)

    def getPairs(word):
        result = []
        for idx in range(0,len(word)):
            pair = word[idx:idx+2]
            if pair.isalpha() and len(pair)==2:
                result.append(pair.upper())
        return result

    str1_lst = getPairs(str1)
    str2_lst = getPairs(str2)

    if len(str1_lst)==0 and len(str2_lst)==0:
        return 65536
    result = getJachard(str1_lst, str2_lst)
    result *= 65536
    answer = int(result)
    return answer

회고

• 불필요한 리스트 사용이 많아 보인다, 다만 이번 문제에서는 메모리 공간이 충분해서 통과됐다.
• 코드를 냅다 쓰고, 조건을 적용해버려서 코드가 꼬일 뻔 했다..
• 앞으로는, 문제 조건이랑 예시 부터 잘 이해하고 구조를 짤 것 => 어느 정도 경험치가 필요해 보이긴 한다.
• 그래도 난이도 중, lv2 문제를 스스로 푼 건 칭찬

주요 문법

.isalpha() : 문자열이 알파벳(대소 구분X)으로만 이루어졌는지 판단하는 메서드
union연산자 | : 집합 연산자 중 하나로, 합집합 요소들을 찾아준다. 다만 set형에서 쓸 수 있고, Counter 라이브러리로 반환되는 자료형에도 사용이 가능하다.
intersection연산자 & : 위와 마찬가지, 다만 교집합 요소들을 찾는다. 집합 연산자들의 활용은 아래 코드에서 볼 수 있다.

배울 코드 (다른 분 코드 참고)

from collections import Counter
def solution(str1, str2):
    # make sets
    s1 = [str1[i:i+2].lower() for i in range(len(str1)-1) if str1[i:i+2].isalpha()]
    s2 = [str2[i:i+2].lower() for i in range(len(str2)-1) if str2[i:i+2].isalpha()]
    if not s1 and not s2:
        return 65536
    c1 = Counter(s1)
    c2 = Counter(s2)
    answer = int(float(sum((c1&c2).values()))/float(sum((c1|c2).values())) * 65536)
    return answer

• 리스트가 비어 있는 것을 if not 리스트 로 표현한 것이 인상적
• Counter 반환 자료형에 집합 연산자 사용한 것도 배울 점

배울 코드 (JS 코드, 출제의도에서 밝혔듯 merge sort를 활용)

function solution(str1, str2) {
    const union = (arr1, arr2) => {
        let mArr = [];
        let lIdx = 0;
        let rIdx = 0;
        while(lIdx < arr1.length && rIdx < arr2.length){
            if(arr1[lIdx] < arr2[rIdx]){
                mArr.push(arr1[lIdx]);
                lIdx++;
            } else if (arr1[lIdx] === arr2[rIdx]){
                mArr.push(arr1[lIdx]);
                lIdx++;
                rIdx++;
            } else {
                mArr.push(arr2[rIdx]);
                rIdx++;
            }
        }
        for( lIdx ; lIdx < arr1.length ; lIdx++ ){
            mArr.push(arr1[lIdx]);
        }
        for( rIdx ; rIdx < arr2.length ; rIdx++ ){
            mArr.push(arr2[rIdx]);
        }
        return mArr;
    }
    const intersection = (arr1, arr2) => {
        let iArr = [];
        let lIdx = 0;
        let rIdx = 0;
        while(lIdx < arr1.length && rIdx < arr2.length){
            if(arr1[lIdx] < arr2[rIdx]){
                lIdx++;
            } else if (arr1[lIdx] > arr2[rIdx]){
                rIdx++;
            } else {
                iArr.push(arr1[lIdx]);
                lIdx++;
                rIdx++;
            }
        }
        return iArr;
    }
    const toArr = (str) => {
        const result = [];
        const convStr = str.replace(/[^a-zA-Z]/g, " ");
        for( let i = 0 ; i < str.length - 1 ; i++ ){
            if(convStr[i] !== " " && convStr[i+1] !== " "){
                const strItem = convStr.slice(i, i+2);
                result.push(strItem.toLowerCase());
            }
        }
        return result;
    }

    const strToArr1 = toArr(str1).sort();
    const strToArr2 = toArr(str2).sort();
    if(strToArr1.length === 0 && strToArr2.length === 0) return 65536;
    const unionArr = union(strToArr1, strToArr2);
    const intersectionArr = intersection(strToArr1, strToArr2);
    return parseInt((intersectionArr.length/unionArr.length)*65536);
}

• 병합정렬 : 부분적으로 정렬 하고, 병합해나감

(참고 자료 - 잔재미코딩님 블로그)[https://www.fun-coding.org/Chapter15-mergesort.html#gsc.tab=0]