🔗 문제 링크
프로그래머스 - 뉴스 클러스터링
⏰ 소요된 시간
20분
✨ 수도 코드
1. 문제 이해
자카드 유사도 J(A, B) * 65536에서 소수점 아래 수는 버리고 출력하는 문제이다.
조건
- 문자열 str1, str2를 인접하는 두 문자씩 잘라서 집합을 구성한다.
- 이때, 영문자를 제외한 다른 문자나 공백이 들어있다면 제거한다.
- 대문자와 소문자는 구분하지 않는다.
- 예시
aa1+aa2,AAAA12- ["AA", "AA"], ["AA", "AA", "AA"]
- 집합 A와 집합 B가 모두 공집합인 경우에는 나눗셈이 정의되지 않으므로 J(A,B) = 1로 정의한다.
- 이때, 주의해야 할 점이 두 집합이 공집합인 경우에만 두 집합의 합집합 크기가 0이 되므로 나눗셈의 분모가 0이 되므로 나눗셈을 정의하지 못한다는 것이다. 따라서, 두 집합 모두가 공집합 경우에만 J(A, B)를 1로 정의해야 한다.
- 즉, 집합 A나 집합 B 중 하나만 0인 경우에는 위의 조건이 만족하지 않는다. 그저 J(A, B)를 0으로 처리해주면 된다. 왜냐하면, 두 집합의 교집합은 공집합일 것이기 때문이다.
- 자카드 유사도 J(A, B) = 두 집합의 교집합 크기 / 두 집합의 합집합 크기
2. 코드 분석
answer = 0
list1, list2 = [], []
for a in range(len(str1)-1):
if (slice_a := str1[a:a+2]).isalpha():
list1.append(str1[a:a+2].upper())
for b in range(len(str2)-1):
if (slice_b := str2[b:b+2]).isalpha():
list2.append(str2[b:b+2].upper())문자열을 두 글자씩 잘라서 알파벳으로만 구성된 경우에만 각각의 집합에 추가해준다.
total = len(list1) + len(list2)
duplication = 0
for i in list1:
if i in list2:
list2.remove(i)
duplication += 1두 집합의 크기의 합인 total과 두 집합의 교집합의 크기인 duplication을 정의한다.
집합 A(list1)의 각 원소가 집합 B(list2)에 있다면, 집합 B에 해당 원소를 지워주고 duplication에 1을 추가해준다. 이때, 집합 B에 해당 원소를 지워주는 이유는 교집합에 이미 추가된 원소로 생각하여야 하기 때문이다. 좀 더 자세하게 말하자면, ["AA", "AA", "BB"], ["AA"]의 교집합은 ["AA"]이지, ["AA", "AA"]가 아니라는 것이다. 그러므로 동일한 원소가 나타난다면, 두 집합 중 하나의 집합에서 해당 원소를 지워야 한다.
if len(list2) == 0 or total == duplication:
return 65536
answer = floor(duplication / (total - duplication) * 65536)이떄, 위에서 언급한 주의해야 할 점을 상기하여야 한다.
- 집합 A와 집합 B가 모두 공집합인 경우에는 나눗셈이 정의되지 않으므로 J(A,B) = 1로 정의한다.
- 이때, 주의해야 할 점이 두 집합이 공집합인 경우에만 두 집합의 합집합 크기가 0이 되므로 나눗셈의 분모가 0이 되므로 나눗셈을 정의하지 못한다는 것이다. 따라서, 두 집합 모두가 공집합 경우에만 J(A, B)를 1로 정의해야 한다.
- 즉, 집합 A나 집합 B 중 하나만 0인 경우에는 위의 조건이 만족하지 않는다. 그저 J(A, B)를 0으로 처리해주면 된다. 왜냐하면, 두 집합의 교집합은 공집합일 것이기 때문이다.
이때 문제를 가볍게 보고 지나갔더니 테스트케이스 5에서 틀렸다고 떴다. 알고 봤더니 조건문을 다음과 같이 작성하였기 때문이었다.
if len(list1) == 0 or len(list2) == 0 or total == duplication:어라? 뭔가 문제풀때 그냥 len(list1) == 0을 지웠더니 통과해서 그냥 그렇구나하고 지나갔는데, 지금 생각해보니 운좋게 테스트케이스를 통과한 것 같네요?
두 집합 모두 공집합인 경우이거나 합집합과 교집합의 크기가 같아 J(A, B)가 1이 되는 경우에만 65536을 반환해야 합니다. 그래서 실제 조건은 다음과 같이 되겠네요.
if (len(list1) == 0 and len(list2) == 0) or total == duplication:
return 65536이 부분만 수정해서 다시 제출해보니 잘 통과되네요~
3. 전체 코드
from math import floor
def solution(str1, str2):
answer = 0
list1, list2 = [], []
for a in range(len(str1)-1):
if (slice_a := str1[a:a+2]).isalpha():
list1.append(str1[a:a+2].upper())
for b in range(len(str2)-1):
if (slice_b := str2[b:b+2]).isalpha():
list2.append(str2[b:b+2].upper())
total = len(list1) + len(list2)
duplication = 0
for i in list1:
if i in list2:
list2.remove(i)
duplication += 1
if (len(list1) == 0 and len(list2) == 0) or total == duplication:
return 65536
answer = floor(duplication / (total - duplication) * 65536)
return answer[썸네일 출처: https://www.kakaocorp.com/page/]
