[프로그래머스 2018 KAKAO BLIND RECRUITMENT] [1차] 뉴스 클러스터링(Lv.2) - 파이썬(Python)

문제

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

프로그래머스

 

문제 풀이

1. makeJ 함수

def makeJ(str):
    alphabet = ['Q','W','E','R','T','Y','U','I','O','P','A','S','D','F','G','H','J','K','L','Z','X','C','V','B','N','M']
    
    strArr = []
    for i in range(1, len(str)):
        if str[i-1] in alphabet and str[i] in alphabet:
            strArr.append(str[i-1]+str[i])
    
    return strArr

• makeJ 함수는 입력된 문자열에서 두 글자씩 끊어 다중집합을 만듭니다. 단, 두 글자가 모두 영문자일 경우에만 다중집합에 추가됩니다.
• alphabet 리스트는 대문자 알파벳을 저장한 리스트로, 두 글자가 모두 이 리스트에 속하는지 확인합니다.
• 문자열을 두 글자씩 잘라서 다중집합 strArr에 추가하는데, 여기서는 str[i-1] 과 str[i]로 두 글자를 조합한 후 배열에 추가합니다.

2. 대문자 변환 및 다중집합 생성

def solution(str1, str2):
    answer = 0
    
    # 대문자로 맞추고 다중집합 생성
    str1Arr = makeJ(str1.upper()) 
    str2Arr = makeJ(str2.upper())

• 입력된 두 문자열 str1 과 str2를 대문자로 변환하여 makeJ 함수를 통해 각각의 다중집합을 만듭니다.
• str1Arr와 str2Arr는 각각의 다중집합을 저장하는 리스트입니다.

3. 교집합 및 합집합 계산

    a = []      # 교집합
    b = []      # 합집합
    
    # 교집합 구하기
    for i in str1Arr:
        if i in str2Arr and i not in a:
            minStrLen = min(str1Arr.count(i), str2Arr.count(i))
            for j in range(minStrLen):
                a.append(i)
            # 합집합에서 쓸 max 버전
            maxStrLen = max(str1Arr.count(i), str2Arr.count(i))
            for j in range(maxStrLen):
                b.append(i)

• a: 교집합을 저장하는 리스트
• b: 합집합을 저장하는 리스트

1. 교집합 구하기:
   • str1Arr에 있는 원소 중 str2Arr에도 존재하는 원소를 찾습니다.
   • 해당 원소가 이미 a(교집합) 리스트에 없다면, 그 원소의 최소 등장 횟수만큼 a리스트에 추가합니다.
   • 합집합에서 쓸 수 있도록 그 원소의 최대 등장 횟수 만큼 b리스트에 추가합니다.
2. 나머지 합집합 원소 추가

    # 합집합 구하기
    for i in str1Arr:
        if i not in a:
            b.append(i)
    for i in str2Arr:
        if i not in a:
            b.append(i)

• 교집합에 없는 원소를 str1Arr과 str2Arr에서 찾아서 b(합집합)에 추가합니다.

4. 자카드 유사도 계산 및 변환

    if len(a) == 0 and len(b) == 0:
        answer = 1
    else:
        answer = len(a)/len(b)
    
    answer = int(answer*65536)
    
    return answer

 

• 교집합과 합집합이 모두 비어 있는 경우(두 다중집합이 공집합), 유사도는 1로 처리합니다.
• 그렇지 않다면, 교집합 크기 / 합집합 크기로 자카드 유사도를 계산합니다.
• 유사도에 65536을 곱한 후, 소수점 아래를 버리고 정수로 반환합니다.

 

최종 정답 코드

 

def makeJ(str):
    alphabet = ['Q','W','E','R','T','Y','U','I','O','P','A','S','D','F','G','H','J','K','L','Z','X','C','V','B','N','M']
    
    strArr = []
    for i in range(1, len(str)):
        if str[i-1] in alphabet and str[i] in alphabet:
            strArr.append(str[i-1]+str[i])
    
    return strArr

def solution(str1, str2):
    answer = 0
    
    # 대문자로 맞추고 다중집합 생성
    str1Arr = makeJ(str1.upper()) 
    str2Arr = makeJ(str2.upper())
    
    a = []      # 교집합
    b = []      # 합집합
    
    # 교집합 구하기
    for i in str1Arr:
        if i in str2Arr and i not in a:
            minStrLen = min(str1Arr.count(i), str2Arr.count(i))
            for j in range(minStrLen):
                a.append(i)
            # 합집합에서 쓸 max 버전
            maxStrLen = max(str1Arr.count(i), str2Arr.count(i))
            for j in range(maxStrLen):
                b.append(i)
    
    
    # 합집합 구하기
    for i in str1Arr:
        if i not in a:
            b.append(i)
    for i in str2Arr:
        if i not in a:
            b.append(i)
    
    if len(a) == 0 and len(b) == 0:
        answer = 1
    else:
        answer = len(a)/len(b)
    
    answer = int(answer*65536)
    
        
    return answer