문제 보기 · Level 2 · 2018 KAKAO BLIND RECRUITMENT (1차) · 정답률 64% · 푼 사람 23,971명 (2026-09-30 기준)1
문제
두 문자열을 두 글자씩 끊어 다중집합(같은 원소가 여러 번 들어갈 수 있는 집합)을 만든다. 영문자로만 된 쌍만 쓰고, 대소문자는 구분하지 않는다. 자카드 유사도는 교집합 크기 ÷ 합집합 크기다. 다중집합의 교집합은 원소마다 개수의 최솟값, 합집합은 최댓값을 쓴다. 유사도에 65536을 곱해 소수점 아래를 버린 값을 돌려준다.
- 문자열 길이 2~1,000
- 두 집합이 모두 공집합이면 유사도를 1로 본다
풀이
막히면 한 단계씩 펼친다2.
필요한 개념
1단계 · 작은 예로 손으로 풀기
“aab”와 “abb”
- “aab” → aa, ab → {aa: 1, ab: 1}
- “abb” → ab, bb → {ab: 1, bb: 1}
- 교집합: 원소마다 개수의 최솟값 → {ab: 1}, 크기 1
- 합집합: 원소마다 개수의 최댓값 → {aa: 1, ab: 1, bb: 1}, 크기 3
- 1/3 × 65536 = 21845.33… → 21845
2단계 · 가장 단순한 방법과 그 속도
문자열이 1,000자라 쌍은 최대 999개다. 어떻게 세어도 빠르다. 이 문제의 핵심은 “다중집합”을 정확히 다루는 것이다. 보통 집합(set)을 쓰면 같은 쌍이 여러 번 나올 때 한 번으로 세어 틀린다.
3단계 · 핵심 아이디어
- 쌍 만들기: 소문자로 바꾼 뒤
s[i:i+2]를 i = 0부터 끝에서 두 번째까지 만든다. 두 글자가 모두 영문자인 쌍만 남긴다(isalpha). - 다중집합 = Counter: 쌍마다 몇 번 나왔는지 세는
Counter로 만든다. 그러면a & b가 교집합(개수의 최솟값),a | b가 합집합(최댓값)이 된다. 크기는 개수의 합이다. - 나누기: 합집합이 비었으면 65536. 아니면
교집합 × 65536 // 합집합. 실수 나눗셈을 거치지 않고 정수로 계산하면 소수점 버리기에서 오차가 없다.
4단계 · 코드 흐름
- 문자열을 받아 영문자 쌍의 Counter를 돌려주는 함수를 만든다.
- 두 문자열의 Counter a, b를 만든다.
- 교집합 크기 =
sum((a & b).values()), 합집합 크기 =sum((a | b).values()). - 합집합이 0이면 65536, 아니면
교 * 65536 // 합을 돌려준다.
5단계 · 파이썬 코드
from collections import Counter
def solution(str1, str2):
def pairs(s):
s = s.lower()
return Counter(s[i:i + 2] for i in range(len(s) - 1) if s[i:i + 2].isalpha())
a, b = pairs(str1), pairs(str2)
inter = sum((a & b).values()) # 개수의 최솟값들의 합
union = sum((a | b).values()) # 개수의 최댓값들의 합
if union == 0:
return 65536
return inter * 65536 // union
Counter(... for ... if ...): 조건에 맞는 쌍만 세어 담는다..isalpha(): 두 글자가 모두 문자면 참이다. 공백·숫자·기호가 섞이면 거짓이다.(a & b).values(): 교집합 Counter의 개수들이다. 더하면 크기가 된다.
6단계 · 실행 추적
“FRANCE”와 “french”
- a = {fr, ra, an, nc, ce} 각 1개
- b = {fr, re, en, nc, ch} 각 1개
- 교집합 {fr, nc} → 2, 합집합 8개 → 2 × 65536 // 8 = 16384
7단계 · 복잡도와 흔한 실수
두 문자열 길이만큼 훑으니 \(O(n)\)이다.
set으로 만들어 같은 쌍의 개수를 잃는다. “aa1+aa2”와 “AAAA12”에서 {aa, aa}와 {aa, aa, aa}의 교집합은 2, 합집합은 3이다.- 대소문자를 구분한다.
int(inter / union * 65536)처럼 실수로 계산하면 드물게 오차로 1 작은 값이 나올 수 있다. 정수로 곱한 뒤 나눈다.- 둘 다 비었을 때(유효한 쌍이 없을 때)를 처리하지 않아 0으로 나눈다.
검증: 문제의 예시 4개를 통과했고, 무작위 문자열 쌍 3,000개에서 “모든 쌍 종류마다 최솟값·최댓값을 직접 세고 분수로 계산하는” 느린 풀이와 결과가 같았다 — 04_pg17677_p1.py