[2018 KAKAO BLIND RECRUITMENT / 프로그래머스] 17677번 : [1차] 뉴스 클러스터링

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

 

Lv2 문제다! 대부분의 로직은 작성했지만, 교집합 구하는 로직이 의도와 잘 맞지 않아 고생을 약간 했던 문제다

 

문제 이해 

1. 모든 문자는 소문자로 처리해야하므로 str1, str2에 모두 lower()를 적용시킨다

 

2. str1을 알파벳으로 두개씩 처리한 문자열들을 담을 리스트를 one, str2는 two로 설정했다

 

3. i -1번째와 i 번째 문자가 모두 소문자 알파벳인 경우에 리스트에 추가한다

 

4-1. one, two 리스트 모두 원소가 없다면 문제 조건에 따라 65536을 반환해준다

 

4-2. 원소가 각각 있다면 이제 one과 two의 공통 원소를 intersection 리스트에 추가한다

처음에는 두 리스트에 모두 있는 원소를 찾아서 넣었는데 같은 값이 중복될 수 있으므로 공통 값을 intersection에 넣어준 뒤 one, two 중에 더 긴 리스트에서 공통 원소들을 하나씩 pop해준다. 

반례 ['ab', 'ab', ' cd'], ['ab','ef'] -> 실제 공통인 원소는 'ab'하나 인데 두 리스트에 있는 원소만 식별하면 'ab' 두개가 intersection에 들어간다 

 

5. 합집합 = len(one) + len(two) - len(intersection)을 계산한 후  (union // intersection) * 65536를 반환한다 

 

- 정답 풀이 

def solution(str1, str2):
    #글자를 두개씩 쪼개기 
    str1 = str1.lower()
    str2 = str2.lower()
    
    one, two = [], []    
    for i in range(1, len(str1)):
        if 97 <= ord(str1[i - 1]) <= 122:
            if 97 <= ord(str1[i]) <= 122:
                one.append(str1[i - 1:  i + 1])
                
    for i in range(1, len(str2)):
        if 97 <= ord(str2[i - 1]) <= 122:
            if 97 <= ord(str2[i]) <= 122:
                two.append(str2[i - 1:  i + 1])

    if len(one) == 0 and len(two) == 0:       
        return 65536
    else:
        #교집합 원소 구하는데 약간 애 먹음
        intersection = []    
        union = len(one) + len(two)
        if len(one) < len(two):
            for i in range(len(one)):
                if one[i] in two:
                    intersection.append(one[i])
                    two.pop(two.index(one[i]))
        else:
            for i in range(len(two)):
                if two[i] in one:
                    intersection.append(two[i])
                    one.pop(one.index(two[i]))
                    
        union -= len(intersection)
        answer = int((len(intersection) / union) * 65536)
        
        return answer

 

- 시도해본 풀이 

61퍼센트에서 틀렸다

def solution(str1, str2):
    #글자를 두개씩 쪼개기 
    str1 = str1.lower()
    str2 = str2.lower()
    
    one, two = [], []    
    for i in range(1, len(str1)):
        if 97 <= ord(str1[i - 1]) <= 122:
            if 97 <= ord(str1[i]) <= 122:
                one.append(str1[i - 1:  i + 1])
                
    for i in range(1, len(str2)):
        if 97 <= ord(str2[i - 1]) <= 122:
            if 97 <= ord(str2[i]) <= 122:
                two.append(str2[i - 1:  i + 1])

    if len(one) == 0 and len(two) == 0:       
        return 65536
    else:
        intersection = []    
        change_one = []
        for each in one:
            if each in two:
                intersection.append(each)
            else:
                change_one.append(each)
            
        union = change_one + two
        
        answer = int((len(intersection) / len(union)) * 65536)
        
        return answer