프로그래머스 - 뉴스 클러스터링 (2018 KAKAO BLIND RECRUITMENT) [Python]

 문제

 

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

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

 

 문제 상황

 

- 1. 대소문자의 차이는 무시한다.

  2. 입력으로 들어온 2글자 이상, 1000글자 이하의 문자는 2글자씩 끊어서 다중 집합으로 만든다.

  3. 공백, 숫자, 특수문자 등은 처리하지 않고 무시하고 넘어간다.

  4. 중복이 허용되기 때문에 파이썬의 set 자료형을 쓸 수 없다.

 

 

 

 해결 전략

 

- 자카드 유사도를 구하는 함수와 주어진 string에서 set을 만드는 함수를 따로 만들어 연산한다.

 

 

 

 코드

 

# 문제를 잘못읽어 시간낭비가 엄청났다..
# 공백이 들어가면 다음 문자를 넣는 것이 아니라 아예 그 쌍 자체를 버려야 한다.
# 구해야 하는 값 = 자카드 유사도
def J(set1, set2):
    # 둘다 비어있는 집합이면 결과가 1이 된다.
    if not set1 and not set2:
        return 1
    # 넘겨받은 set를 이용해서 자카드 유사도를 구한다.
    # 자카드 유사도가 (교집합 길이 / 합집합 길이) 이므로 교집합 길이만 구하면 된다.
    # 문자열의 길이가 최대 1000이므로 set의 최대 개수는 최대 999개이고 
    # O(N^2) 에도 1000000 이므로 충분히 커버 가능한 속도가 된다.
    intersection = 0
    checked = [False] * len(set2)
    for i in range(len(set1)):
        for j in range(len(set2)):
            # set1의 첫번째 글자가 set2의 첫번째 글자보다 뒤에 있는 글자면 더 비교해볼 의미가 없다.
            # break를 넣어줘야 겹치는 문자가 있을 경우 중복되지 않는다.
            if set1[i] == set2[j] and not checked[j]:
                checked[j] = True
                intersection += 1
                break
    
    return intersection/(len(set1)+len(set2)-intersection)
 
 
def solution(str1, str2):
    # 입력받은 string 값을 이 함수에서 set로 만들어 J함수에 넘겨준다.
    # 우선 전부 소문자로 만들어 준 뒤, 공백, 특수문자를 무시하며 2개씩 나누어 저장한다.
    str1, str2 = str1.lower(), str2.lower()
    set1, set2 = [], []
    idx = 0
    # 2개씩 묶을 임시 리스트
    temp = []
    # str1
    while idx < len(str1):
        # str1[idx]의 ord 값이 97이상 122 이하면 temp에 추가
        if 97 <= ord(str1[idx]) <= 122:
            temp.append(str1[idx])
            # temp의 길이가 2이면 set에 추가하고 temp의 1번 인덱스값만 temp에 넣어주는 초기화 진행
            if len(temp) == 2 :
                set1.append(temp)
                temp = [temp[1]]  
        else :
            temp = []
        # idx 1 증가
        idx += 1
        
        
    idx2 = 0
    temp2 = []
    # str2   
    while idx2 < len(str2):
        # str2[idx]의 ord 값이 97이상 122 이하면 temp에 추가
        if 97 <= ord(str2[idx2]) <= 122:
            temp2.append(str2[idx2])
            if len(temp2) == 2 :
                set2.append(temp2)
                temp2 = [temp2[1]]
        else :
            temp2 = []
        # idx 1 증가
        idx2 += 1
        # temp의 길이가 2이면 set에 추가하고 temp의 1번 인덱스값만 temp에 넣어주는 초기화 진행
        # idx가 len(str1)인데 temp가 비어있지 않으면 set에 temp 추가
        
    return int(J(set1, set2)*65536)
 
 

 

 

 해설

 

- 조건을 통해 idx2, temp2 같은 변수를 안만들 수 있었지만 코드 리딩에 직관적이기 위해 변수를 추가하였다. 단순 시뮬레이션에 가까운 문제이다.

 

 

 

 새로 학습한 것 & 실수 

 

- 문제를 제발 읽는 시간에 많은 시간을 투자하자

 

- 중간 과정을 하나하나 찍어보며 뭐가 문제인지 찾아냈다. 테스트케이스가 많아서 찾아낼 수 있었다.

 

 

출처 - https://programmers.co.kr/learn/courses/30/lessons/17677?language=python3