프로그래머스 Lv2 문제입니다. 실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.

문제

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

[나의 풀이]

⌛ 시간 초과 (69.2/100점)

import re
import math

def get_words(str_n):

    words = []
    
    check = r'[^a-zA-Z]'
    
    same_cnt = 1
    for i in range(len(str_n)-1):
        
        word = str_n[i]+str_n[i+1]
        
        if re.sub(check,"",word) != word:
            print("word : ",word)
            print("탐지!")
            continue
        
        word = word.upper()
        
        # if word in words:
        #     word += str(same_cnt)
        #     same_cnt += 1
        
        if word in words:
            tmp = str(same_cnt)+word
            same_cnt += 1
            word = tmp
        
        words.append(word)
    
    return words

def get_Jaccard(words1,words2):
    
    inter = list(set(words1) & set(words2))
    union = list(set(words1) | set(words2))
    
    jaccard = len(inter)/len(union)
    return len(inter)/len(union)

def solution(str1, str2):
    
    words1 = get_words(str1)
    print(words1)
    words2 = get_words(str2)
    print(words2)
    
    if words1==[] and words2==[]:
        return 65536
    
    jaccard = get_Jaccard(words1,words2)
    print(jaccard)
    print(math.floor(jaccard*65536))
    
    return math.floor(jaccard*65536)

중복 원소를 허용하는 두 집합의 자카드 유사도를 구하는 문제입니다. 이때 각 집합의 원소는 주어지는 각 문자열을 통해 만들어집니다. 예를 들어, 'FRANCE', 'french' 와 같은 문자열이 입력된다면 이어지는 두 영문자씩 쌍을 지어 한 원소가 됩니다. 이때, 특수문자나 숫자는 해당이 안되기 때문에 정규식으로 처리해주었습니다.🐺🐺🐺

다음으로 각 집합에 동일한 문자열 원소이더라도 중복이 가능하게끔 구현하기 위해 이전에 동일한 원소가 있다면 +n씩 더하는 방식으로 연산하였는데 일부케이스에서 실패하여 오랜고민 끝에 다른 풀이를 참고하여 이유를 알게 되었습니다.

위 풀이로 구현시 'aa+aa+bb+bb','AAAA+BBBB' 와 같이 입력될 때 제가 원하는 결과는

words1= ['aa', 'aa@', 'bb', 'bb@']
words2 = = ['aa', 'aa@', 'aa@@', 'bb', 'bb@', 'bb@@']

이지만 서로 다른 원소이더라도 이전에 동일한 원소가 탐지될 때마다 same_cnt +=1 하기 때문에

words1 = ['aa', 'aa@', 'bb', 'bb@@'] 
words2 =  ['aa', 'aa@', 'aa@@', 'bb', 'bb@@@', 'bb@@@@' ]

으로 저장되는 것이 문제라는 것을 깨닫게 되었습니다.

[다른 사람의 풀이1]

from collections import Counter

def solution(str1, str2):
    str1_low = str1.lower()
    str2_low = str2.lower()
    
    str1_lst = []
    str2_lst = []
    
    for i in range(len(str1_low)-1):
        if str1_low[i].isalpha() and str1_low[i+1].isalpha():
            str1_lst.append(str1_low[i] + str1_low[i+1])
    for j in range(len(str2_low)-1):
        if str2_low[j].isalpha() and str2_low[j+1].isalpha():
            str2_lst.append(str2_low[j] + str2_low[j+1])
            
    Counter1 = Counter(str1_lst)
    Counter2 = Counter(str2_lst)
    
    inter = list((Counter1 & Counter2).elements())
    union = list((Counter1 | Counter2).elements())
    
    if len(union) == 0 and len(inter) == 0:
        return 65536
    else:
        return int(len(inter) / len(union) * 65536)
    
# solution('FRANCE','french')
solution('aa1+aa2','AAAA12')

영문자만을 추출하기 위해 isalpha()함수를 사용하고 Counter()를 활용하여 교/합집합을 구현한 풀이입니다.

두 Counter() 객체에 집합의 영문자 요소를 저장한 뒤Counter()간의 &연산을 통해 교집합을 구하고 |연산을 통해 합집합을 구하는 방식입니다. 마지막 교집합/합집합.elements()을 리스트로 형변환하여 자카드 유사도를 구할 수 있었습니다.🧸🧸🧸

[다른 사람의 풀이2]

import re
import math

def solution(str1, str2):

    str1 = [str1[i:i+2].lower() for i in range(0, len(str1)-1) if not re.findall('[^a-zA-Z]+', str1[i:i+2])]
    str2 = [str2[i:i+2].lower() for i in range(0, len(str2)-1) if not re.findall('[^a-zA-Z]+', str2[i:i+2])]

    gyo = set(str1) & set(str2)
    hap = set(str1) | set(str2)

    if len(hap) == 0:
        return 65536

    gyo_sum = sum([min(str1.count(gg), str2.count(gg)) for gg in gyo]) # 교
    hap_sum = sum([max(str1.count(hh), str2.count(hh)) for hh in hap]) # 합

    return math.floor((gyo_sum/hap_sum)*65536)

가장 파이써닉하고 간결한 풀이였습니다.

먼저 2글자의 영문자로만 이루어진 리스트 str1, str2를 각각 구합니다. 그 후 중복없는 교/합집합을 구합니다. 마지막으로 중복있는 교집합을 구하기 위해 중복없는 교집합의 요소가 있는 str1,str2별 갯수의 최솟값들을 더하고 합집합을 구하기 위해 str1,str2별 갯수의 최대값들을 더하는 풀이입니다.🐰🐰🐰

중복없는 교/합집합을 활용하여 중복있는 교/합집합을 구하는 아이디어 자체가 좋았던 풀이입니다.

감사합니다.