[코딩테스트] - 2018 카카오 블라인드 : 뉴스 클러스터링

네이버 부캠 2차 코테 준비겸 알고리즘 문제를 풀고 있는데

 

뭘 풀어야할지 감이 안와서 그냥 프로그래머스 레벨 2문제 쭉 풀다가 시험 볼 예정이다.

 

저번 1차때 프로그래머스 플랫폼에서 시험을 보는게 익숙치 않고, 보통은 내가 주로 사용하는 IDE에서 코딩 돌려보다가 안되면 이것저것 출력해보면서 오류나는 곳을 찾는데, 그것도 여의치 않은 환경에서 시험을 봐야하니 익숙해져야 할 필요가 있겠더라.

 

아 내일은 자료구조 구현도 좀 연습을 해야겠다.

 

설마 BFS, DFS도 나오려나 하...

나같은 비전공자에게 알고리즘은 너무 높은 벽이다....

 

 

 

아무튼 문제 해설 들어가보겠다

 

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

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

 

우선 한번씩 풀어본 이후에 코드를 보는 것이 좋을 거 같아 링크를 가져왔다.

 

문제만 읽고서는 뭐야 그냥 교집합, 합집합만 찾아서 계산하면 되겠네, 싶어 금방 끝나겠구나 했는데,

 

생각보다는 오래걸렸다. 

 

def solution(str1, str2):
    lst1 = []
    lst2 = []
    str1 = str1.lower()
    str2 = str2.lower()
    for i in range(len(str1)-1):
        if not str1[i].isalpha():
            continue
        if not str1[i+1].isalpha():
            continue
        lst1.append(str1[i:i+2])
    for i in range(len(str2)-1):
        if not str2[i].isalpha():
            continue
        if not str2[i+1].isalpha():
            continue
        lst2.append(str2[i:i+2])
    inter = []
    tmp = []
    for item in lst1:
        if item in tmp:
            continue
        f_count = lst1.count(item)
        if item in lst2:
            s_count = lst2.count(item)
            if f_count > s_count:
                for i in range(s_count):
                    inter.append(item)
            else:
                for i in range(f_count):
                    inter.append(item)
        tmp.append(item)

    if len(lst1) + len(lst2) - len(inter) == 0:
        return 65536
    answer = int((len(inter)/(len(lst1) + len(lst2) - len(inter))) * 65536)
    return answer

 

처음에 몇몇 테스트에서 실패가 떠서 뭐지 하고 살펴보다가

원래는 교집합, 합집합 개수를 다 따로 찾은 후에 계산했는데, 생각해보니 합집합 개수를 따로 셀 필요가 없더라

 

그냥 집합 A, B더해서 교집합 개수 빼면되는데. 

수학을 놓은지 너무 오래됐다.

 

아무튼 이 부분만 바꿨더니 바로 통과 되었다.

 

코드 구성은 간단하다.

먼저 대소문자 구분 안한다고 했으니 전부 소문자로 바꿔주고

처음 두개의 for문은 각각의 문자열에서 특수문자, 숫자 제외하고 오로지 문자열로만 이루어진 원소를 뽑아 리스트에 저장시키는 과정이다.

 

그리고 마지막 for문은 교집합 찾는 과정. 

문제 설명 보면 중복되는 원소도 따로 세어줘야 해서 집합 자료형은 사용할 수 없다.

 

마지막은 계산이다. 합집합이 0인 경우는 zerodivision 에러가 발생하기 때문에 이경우는 문제에서 1로 도출하라고 해서 그렇게 예외 처리를 해주었다.

 

 

 

2차 코테도 붙었으면 좋겠다. 제발!!!!!!!!!