프로그래머스: [1차] 뉴스 클러스터링 (파이썬, 구현)

우선 문제가 꽤나 길다. 코딩테스트는 수학, 공학문제 풀이와 다르게 풀이를 구현하는데 시간이 꽤나 걸려 문제 조건을 꼼꼼히 읽는 것이 특히 더 중요한 것 같다. 

 

문제에선 자카드 유사도라는 새로운 개념을 소개하고 이를 응용하여 두 문자열의 유사도를 출력할 것을 요구한다. 문제를 읽으면서 집중했던 부분은 크게 네가지이다.

 

첫째로 원소의 중복을 허용하는 다중집합에 대해서도 자카드 유사도를 적용할 수 있다는 것이다. 이는 두 집합간의 교집합을 구할때 중요하다. 왜냐하면 중복을 허용하지 않는다면 리스트를 집합으로 변환 후 뺼셈을 통해 교집합의 원소의 갯수를 쉽게 구할 수 있지만 중복이 있다면 반복문을 통해 교집합을 구해야하므로 교집합을 구하는 구현 방법이 달라진다.

 

둘째로 두 집합이 모두 공집합일 경우 자카드 유사도는 1이라는 것이다. 주어진 문자열을 통해 집합을 만든 후 두 집합 모두 공집합이라면 1을 return하면 된다.(문제에서는 이에 65536을 곱한 65536을 return하면 된다.)

 

셋째로 영문자로 된 글자만 유효하다는 점이다. 문자열을 두 문자씩 끊어서 집합을 만들 때 문자열중 하나라도 영문자가 아니라면 집합에 넣어서는 안된다.

 

마지막으로 대소문자를 구별하지 않는다는 점이다. 나는 집합에 문자를 넣을 때 미리 소문자 변환하여 넣음으로써 이를 해결하였다.

 

네가지 부분에 집중하여 짠 코드는 다음과 같다.

def solution(str1, str2):
    list1, list2 = [], []
    # 두 문자씩 끊어서 list에 넣는다. 이때 두 문자중 하나라도 영문자가 아니면 넣지않고, 넣을때는 소문자 변환하여 넣는다
    for i in range(len(str1) - 1):
        if str1[i].isalpha() and str1[i + 1].isalpha():
            list1.append((str1[i] + str1[i + 1]).lower())

    for j in range(len(str2) - 1):
        if str2[j].isalpha() and str2[j + 1].isalpha():
            list2.append((str2[j] + str2[j + 1]).lower())
            
    # 합집합 원소의 개수를 구하기 위해 미리 두 list의 길이들을 더한다. 왜냐하면 합집합은 전체 원소의 개수- 교집합 원소의 개수이기 때문이다.
    parent = len(list1) + len(list2)
    # 둘다 공집합이라면 65536 return
    if not list1 and not list2:
        return 65536
    # 하나라도 공집합이라면 교집합은 0이므로 0 return
    elif not list1 or not list2:
        return 0
    else:
        child = 0
        if len(list1) >= len(list2):
            for element in list2:
                if element in list1:
                    # 한 list에 있는 원소가 다른 list에 있다면 count를 하나 올린 후 다른 list에서 그 원소를 삭제함으로써 중복연산되는 것을 방지.
                    child += 1
                    del list1[list1.index(element)]
        else:
            for element in list1:
                if element in list2:
                    child += 1
                    del list2[list2.index(element)]
        # 합집합 = 전체 집합 - 교집합
        parent -= child
        return int((child / parent) * 65536)