Level 2 [1차] 뉴스 클러스터링 <KAKAO 2018 BLIND RECRUITMENT>

programmers.co.kr/learn/courses/30/lessons/17677?language=python3

코딩테스트 연습 - [1차] 뉴스 클러스터링

 

최종 코드

• GitHub github.com/hwayeon351/Programmers-Algorithms

hwayeon351/Programmers-Algorithms

from collections import Counter
def solution(str1, str2):
    str1 = str1.lower()
    str2 = str2.lower()
    A = []
    B = []
    i = 0
    #다중 집합 만들기
    while i <= max(len(str1)-2, len(str2)-2):
        if i <= len(str1)-2:
            if str1[i].isalpha() and str1[i+1].isalpha(): A.append(str1[i] + str1[i+1])
        if i <= len(str2)-2:
            if str2[i].isalpha() and str2[i+1].isalpha(): B.append(str2[i] + str2[i+1])
        i+=1
        
    #A와 B가 공집합인 경우
    if len(A) == len(B) == 0: return 65536
    
    #유사도 계산
    counterA = Counter(A)
    counterB = Counter(B)
    inter_AB = 0
    for k in counterA.keys():
        inter_AB += min(counterA[k], counterB[k])
    sum_AB = sum(counterA.values()) + sum(counterB.values()) - inter_AB
    return int(inter_AB/sum_AB*65536)

---

풀이 과정

풀이 시간 54분

 

from collections import Counter
def solution(str1, str2):
	#1. str1, str2 소문자로 변환 -> O(n)
    str1 = str1.lower()
    str2 = str2.lower()
    
    #2. 다중 집합 만들기 -> O(n)
    A = []
    B = []
    i = 0
    while i <= max(len(str1)-2, len(str2)-2):
        if i <= len(str1)-2:
            if str1[i].isalpha() and str1[i+1].isalpha(): A.append(str1[i] + str1[i+1])
        if i <= len(str2)-2:
            if str2[i].isalpha() and str2[i+1].isalpha(): B.append(str2[i] + str2[i+1])
        i+=1

    #3. 유사도 계산
    #A와 B가 공집합인 경우
    if len(A) == len(B) == 0: return 65536
    
    counterA = Counter(A)
    counterB = Counter(B)
    #교집합 개수 구하기 -> O(n)
    inter_AB = 0
    for k in counterA.keys():
        inter_AB += min(counterA[k], counterB[k])
        
    #합집합 개수 구하기 -> O(n)
    sum_AB = sum(counterA.values()) + sum(counterB.values()) - inter_AB
    
    return int(inter_AB/sum_AB*65536)
    
#시간복잡도 = O(n), 공간복잡도 = O(n)

---

이전 풀이

 

def solution(str1, str2):
    str1 = str1.lower()
    str2 = str2.lower()
    arr1 = []
    arr2 = []
    inter = 0
    for i in range(len(str1)-1):
        if (str1[i]+str1[i+1]).encode().isalpha():
            arr1.append(str1[i]+str1[i+1])
    for i in range(len(str2)-1):
        if (str2[i]+str2[i+1]).encode().isalpha():
            arr2.append(str2[i]+str2[i+1])
    if len(arr1) == 0 and len(arr2) == 0: return 65536
    arr1.sort()
    arr2.sort()
    last = ""
    for a in arr1:
        if a == last: continue
        cnt = arr2.count(a)
        if cnt > 1:
            inter += min(cnt, arr1.count(a))
            last = a
            continue
        inter += cnt
        last = a

    return int(inter / (len(arr2) - inter + len(arr1)) * 65536)

 이 문제는 KAKAO 2018 BLIND RECRUITMENT [1차]의 5번째 문제이다.(다른 문제는 아래 참고를 참고하면 된다.)

첫 시도를 했을 때, 입출력 예제는 모두 맞았지만 제출하면서 실패가 몇 군데 떴던걸로 기억한다. 문제를 다시 읽어 보면서 내가 간과했던 부분을 발견했고, 적용하니 무사히 해결할 수 있었다. 문제를 잘 읽자!

내가 간과했던 부분

1. 문자열을 소문자로 바꿔주고, 리스트 및 변수 선언하기

    str1 = str1.lower()
    str2 = str2.lower()
    arr1 = []
    arr2 = []
    inter = 0

 먼저, 문제에서 다중집합 원소 사이를 비교할 때, 대문자와 소문자의 차이를 무시한다고 하였으니 내장 함수인 lower()을 사용해 str1과 str2를 모두 소문자로 바꿔준다. 그 다음, str1과 str2의 다중집합을 담을 arr1과 arr2 리스트를 선언하고, 교집합의 개수를 저장할 변수 inter을 0으로 초기화 한다.

 

 

2. 다중집합 만들기

    for i in range(len(str1)-1):
        if (str1[i]+str1[i+1]).encode().isalpha():
            arr1.append(str1[i]+str1[i+1])
    for i in range(len(str2)-1):
        if (str2[i]+str2[i+1]).encode().isalpha():
            arr2.append(str2[i]+str2[i+1])

 str1과 str2를 각각 두 글자씩 끊어서, 모두 영문자로 된 글자 쌍인지 판별한 후에 arr1과 arr2에 원소를 추가해준다. 이때, 영문자인지 아닌지 판별하기 위해 isalpha()라는 문자열 내장 함수를 사용한다. isalpha() 앞에 encode()를 붙여준 것은 문자열이 한글로 구성되어 있을 때에도 isalpha()의 결과가 True로 나온다고 하여 한글과 영문자까지 구분해주기 위함이다.

 

 

3. 교집합 구하기

    if len(arr1) == 0 and len(arr2) == 0: return 65536
    arr1.sort()
    arr2.sort()
    last = ""
    for a in arr1:
        if a == last: continue
        cnt = arr2.count(a)
        if cnt > 1:
            inter += min(cnt, arr1.count(a))
            last = a
            continue
        inter += cnt
        last = a

    return int(inter / (len(arr2) - inter + len(arr1)) * 65536)

 이제, arr1과 arr2의 교집합을 구해보자. 먼저, 문제에서 제시한 예제 입출력 4번째처럼 영문자 사이 사이에 특수가 있는 경우에는 arr1과 arr2의 사이즈가 0일 것이다.  이 경우를 먼저 체크해줘야 한다.

1. len(arr1) == 0이고, len(arr2) == 0인 경우, return 65536 한다.
2. 위의 경우가 아니라면, arr1과 arr2를 정렬한다. 정렬을 해주는 이유는 원소를 하나씩 비교해가며 교집합을 구해 줄건데, 같은 원소가 여러 개 있는 경우에 교집합을 구하고, 또 다른 원소를 비교해주기 위함이다. for문을 통해 arr1의 원소와 arr2의 원소를 비교하며 다음과 같은 과정을 해준다.
   1. a == last인 경우, 중복 원소를 의미한다. 이미 이전에 arr1과 arr2의 a 개수를 비교하여 최솟값을 inter에 더해줬기 때문에, 또 다시 카운팅할 필요가 없으므로 continue 해준다.
   2. a != last인 경우, arr2에 a 개수를 카운팅하여 cnt를 초기화 한다.
   3. cnt > 1인 경우, 중복 요소이므로 arr1과 arr2의 a 개수를 비교하여 최솟값을 inter에 더해주고, last를 a로 바꿔준다.
   4. cnt < 1인 경우, inter에 cnt를 더해주고, last를 a로 초기화 한다.

위의 과정을 반복해서 교집합의 수 inter을 구했다. 마지막으로 자카드 유사도인 int(inter / (len(arr2) - inter + len(arr1)) * 65536)을 return한다. 

 

---

다른 사람의 풀이 분석

import re

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])]

    inter = set(str1) & set(str2)
    union = set(str1) | set(str2)

    if len(union) == 0 :
        return 65536

    inter_sum = sum([min(str1.count(i), str2.count(i)) for i in inter])
    union_sum = sum([max(str1.count(u), str2.count(u)) for u in union])

    return int((inter_sum/union_sum)*65536)

 

1. 정규 표현식을 지원하는 re모듈의 내장 함수 findall()을 활용하기

 내가 짠 코드와 달리 간단하게 다중집합을 생성했다. 바로 정규식을 이용한 문자열 검색을 활용한 것이다.

    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])]

조건문 if not re.findall('[^a-zA-Z]+', str1[i:i+2])]을 통해 str[i:i+2]가 알파벳이 아닌 경우를 제외함으로써 다중집합을 쉽게 생성했다.

 

 

2. 집합 연산 활용하기

    inter = set(str1) & set(str2)
    union = set(str1) | set(str2)

    if len(union) == 0 :
        return 65536

    inter_sum = sum([min(str1.count(i), str2.count(i)) for i in inter])
    union_sum = sum([max(str1.count(u), str2.count(u)) for u in union])

    return int((inter_sum/union_sum)*65536)

 str1과 str2를 set으로 바꾸어 중복을 없애고, 집합 연산 교집합은 &, 합집합은 |을 활용해서 구한다.

그 다음, 합집합인 union의 사이즈가 0이면 바로 return 65536 하고, 아니면 다시 inter_sum과 union_sum을 구한다.

 

내가 직접 짠 코드와 달리 많이 간결한 것 같다. 정규 표현식에 대해 몰랐는데 덕분에 정규 표현식에 대한 공부를 할 수 있었고, 다음에 비슷한 문제가 나왔을 때 적용할 수 있었으면 좋겠다.

---

참고

• 1. 비밀지도 2021/02/09 - [분류 전체보기] - Level 1 [1차] 비밀지도 Python3

Level 1 [1차] 비밀지도 Python3

• 2. 다트게임 2021/02/09 - [코테 노트/프로그래머스] - Level 1 [1차] 다트게임 Python3

Level 1 [1차] 다트게임 Python3

• 3. 캐시 2021/02/09 - [코테 노트/프로그래머스] - Level 2 [1차] 캐시

Level 2 [1차] 캐시

• 4. 셔틀버스 https://hwayomingdlog.tistory.com/105

Level 3 [1차] 셔틀버스 Python3

• 6. 프랜즈 4블록 2021/02/09 - [분류 전체보기] - Level 2 [1차] 프랜즈 4블록

Level 2 [1차] 프랜즈 4블록

• 7. 추석트래픽 https://hwayomingdlog.tistory.com/106

Level 3 [1차] 추석 트래픽 Python3

---