문제
여러 언론사에서 쏟아지는 뉴스, 특히 속보성 뉴스를 보면 비슷비슷한 제목의 기사가 많아 정작 필요한 기사를 찾기가 어렵다. Daum 뉴스의 개발 업무를 맡게 된 신입사원 튜브는 사용자들이 편리하게 다양한 뉴스를 찾아볼 수 있도록 문제점을 개선하는 업무를 맡게 되었다.
개발의 방향을 잡기 위해 튜브는 우선 최근 화제가 되고 있는 "카카오 신입 개발자 공채" 관련 기사를 검색해보았다.
- 카카오 첫 공채..'블라인드' 방식 채용
- 카카오, 합병 후 첫 공채.. 블라인드 전형으로 개발자 채용
- 카카오, 블라인드 전형으로 신입 개발자 공채
- 카카오 공채, 신입 개발자 코딩 능력만 본다
- 카카오, 신입 공채.. "코딩 실력만 본다"
- 카카오 "코딩 능력만으로 2018 신입 개발자 뽑는다"
기사의 제목을 기준으로 "블라인드 전형"에 주목하는 기사와 "코딩 테스트"에 주목하는 기사로 나뉘는 걸 발견했다. 튜브는 이들을 각각 묶어서 보여주면 카카오 공채 관련 기사를 찾아보는 사용자에게 유용할 듯싶었다.
유사한 기사를 묶는 기준을 정하기 위해서 논문과 자료를 조사하던 튜브는 "자카드 유사도"라는 방법을 찾아냈다.
자카드 유사도는 집합 간의 유사도를 검사하는 여러 방법 중의 하나로 알려져 있다. 두 집합 A, B 사이의 자카드 유사도 J(A, B)는 두 집합의 교집합 크기를 두 집합의 합집합 크기로 나눈 값으로 정의된다.
예를 들어 집합 A = {1, 2, 3}, 집합 B = {2, 3, 4}라고 할 때, 교집합 A ∩ B = {2, 3}, 합집합 A ∪ B = {1, 2, 3, 4}이 되므로, 집합 A, B 사이의 자카드 유사도 J(A, B) = 2/4 = 0.5가 된다. 집합 A와 집합 B가 모두 공집합일 경우에는 나눗셈이 정의되지 않으니 따로 J(A, B) = 1로 정의한다.
자카드 유사도는 원소의 중복을 허용하는 다중집합에 대해서 확장할 수 있다. 다중집합 A는 원소 "1"을 3개 가지고 있고, 다중집합 B는 원소 "1"을 5개 가지고 있다고 하자. 이 다중집합의 교집합 A ∩ B는 원소 "1"을 min(3, 5)인 3개, 합집합 A ∪ B는 원소 "1"을 max(3, 5)인 5개 가지게 된다. 다중집합 A = {1, 1, 2, 2, 3}, 다중집합 B = {1, 2, 2, 4, 5}라고 하면, 교집합 A ∩ B = {1, 2, 2}, 합집합 A ∪ B = {1, 1, 2, 2, 3, 4, 5}가 되므로, 자카드 유사도 J(A, B) = 3/7, 약 0.42가 된다.
이를 이용하여 문자열 사이의 유사도를 계산하는데 이용할 수 있다. 문자열 "FRANCE"와 "FRENCH"가 주어졌을 때, 이를 두 글자씩 끊어서 다중집합을 만들 수 있다. 각각 {FR, RA, AN, NC, CE}, {FR, RE, EN, NC, CH}가 되며, 교집합은 {FR, NC}, 합집합은 {FR, RA, AN, NC, CE, RE, EN, CH}가 되므로, 두 문자열 사이의 자카드 유사도 J("FRANCE", "FRENCH") = 2/8 = 0.25가 된다.
제한 사항
- 입력으로는 str1과 str2의 두 문자열이 들어온다. 각 문자열의 길이는 2 이상, 1,000 이하이다.
- 입력으로 들어온 문자열은 두 글자씩 끊어서 다중집합의 원소로 만든다. 이때 영문자로 된 글자 쌍만 유효하고, 기타 공백이나 숫자, 특수 문자가 들어있는 경우는 그 글자 쌍을 버린다. 예를 들어 "ab+"가 입력으로 들어오면, "ab"만 다중집합의 원소로 삼고, "b+"는 버린다.
- 다중집합 원소 사이를 비교할 때, 대문자와 소문자의 차이는 무시한다. "AB"와 "Ab", "ab"는 같은 원소로 취급한다.
문제를 보고 든 생각
지문이 상당히 길지만 쫄지는 않았다.
다 읽어보니 내용도 할만하다고 생각했고 어떻게 하면 구현할 수 있을 것 같다는 생각이 들었다.
다만 내가 문제를 다 이해했을까라는 의문은 들었다.
요즘 문제를 풀면서 드는 생각은 구현 실력이나 알고리즘을 짜는 실력도 중요하지만
문제를 이해하는 능력도 중요하다는 생각이 든다.
하지만 나는 셋 다 부족한 것 같다.
그럼 어떡해 많이 풀어봐야지 뭐
나의 아이디어
말이 엄청 길지만 결국 교집합, 합집합을 시킬 어떤 문자열 집합을 만들어내라는 문제이다.
교집합, 합집합이라고 하니 딱 두 가지가 떠올랐다.
set과 Counter, 이 두 가지는 파이썬에서 집합 계산을 도와주는 친구들이다.
이 친구들을 이용해서 코드를 짜봐야겠다고 생각했다.
그리고 그냥 구현 문제라고 생각이 들어서 딱히 흐름이나 알고리즘이랄 게 없어 보였다.
결과
string1 = []
string2 = []
for i in range(len(str1) - 1):
if str1[i : i + 2].isalpha():
string1.append(str1[i : i + 2].lower())
for i in range(len(str2) - 1):
if str2[i : i + 2].isalpha():
string2.append(str2[i : i + 2].lower())
# 교집합과 합집합 구하기
counter1 = Counter(string1)
counter2 = Counter(string2)
# 공집합이면 그냥 65536 곱해주기
if len(counter1.keys()) == 0 and len(counter2.keys()) == 0:
answer = 65536
# 같은 원소가 중복으로 있다고 하면 그 원소의 개수의 max값이 합집합의 개수로 포함된다.
else:
union_add = 0
intersect_add = 0
union = 0
duplicated = []
for i, item in enumerate(sorted(counter1.items())):
if item[0] in counter2.keys():
intersect_add = min(item[1], counter2[item[0]]) - 1
union_add = max(item[1], counter2[item[0]]) - 1
duplicated.append(item[0])
for item in sorted(counter1.items()):
if item[0] not in duplicated and item[1] > 1:
union += item[1] - 1
for item in sorted(counter2.items()):
if item[0] not in duplicated and item[1] > 1:
union += item[1] - 1
answer = (len(counter1 & counter2) + intersect_add) / (len(counter1 | counter2) + union_add + union) * 65536
answer = int(answer)
return answer위 코드는 여러 번의 제출 후 수정에 수정을 거친 코드이다.
결과적으로는 13개의 테스트 케이스 중 5개에서 오답 처리를 받았다.
틀릴 때마다 문제를 읽어보니 아무래도 이 문제에서 정답 처리를 받을 수 있도록 도와주는 중요한 포인트는 다중 집합의 구현에 있는 것 같았다.
그래서 Counter로 합집합, 교집합을 모두 구해놓고도 다중 집합을 구현하려고 애를 썼다.
솔직히 다중 집합이 뭔지도 몰라서 다중 집합에 대해서도 찾아봐야만 했다.
물론 찾아보고 나서 구현을 할 때에도 내가 분명 제대로 이해한 게 맞는지 되게 의구심이 들기도 했다.
왜냐하면 계속 5개의 테스트 케이스에서 오답 처리를 받았기 때문이다.
너무나도 답답했다.
어디 부분 때문에 틀린지는 알겠는데
도대체 뭘 어떻게 해야 되는 건지, 어떻게 수정을 해야 되는 건지.
이럴 때 보면 나는 문제 해결력이 많이 부족한 것 같다.
검색을 통해 알게 된 내용
3일간의 고민 끝에 결국 검색을 해봤다.
그런데 정말 욕이 안 나올래야 안 나올 수가 없는 광경을 봐버렸다.
고민의 시간이었던 3일은 삽질 그 자체였다.
알고 보니 그냥 string 배열에 저장된 문자열들을 counter 객체로 만든 후에
그대로 사용하면 됐던 것이었다...
간단하게 말하면, Counter 객체로 만들고 나서 뭘 더 추가해줄 게 없었다.
그냥 그 자체로 다중 집합이 생성이 된 것이었다.
검색을 통해 알게 된 풀이
string1 = []
string2 = []
for i in range(len(str1) - 1):
if str1[i : i + 2].isalpha():
string1.append(str1[i : i + 2].lower())
for i in range(len(str2) - 1):
if str2[i : i + 2].isalpha():
string2.append(str2[i : i + 2].lower())
# 교집합과 합집합 구하기
counter1 = Counter(string1)
counter2 = Counter(string2)
# 이 자체로 다중 집합의 형성이 이루어진 것
intersect = len(list((counter1 & counter2).elements()))
union = len(list((counter1 | counter2).elements()))
if intersect == 0 and union == 0:
print(65536)
else:
print(int(intersect / union * 65536))set과 counter 중 set을 선택하지 않고 counter로 집합 계산을 한 이유가 set은 중복된 요소들을 제거시키는데
counter는 제거시키지 않고 중복된 것이 몇 개가 더 있는지 세어주기 때문이었다.
그냥 그걸 그대로 이용하면 다중 집합의 의미에 일치하는 것이었는데
아무래도 내가 다중 집합을 제대로 이해하지 못했던 것 같다.
그래서 눈 앞에 counter 객체를 보고도 이게 답인지 몰랐겠지.
느낀점
삽질로 배워가는 건 기억에 오래 남는다.
누가 말한 건 아니고 내가 생각한 문장이다.
삽질한 시간이 있으니까 그만큼 기억에 오래 남았으면 좋겠다는 나의 소망이 담겨있다.
이 문제를 통해 Counter 객체를 이용하면 다중 집합을 구현할 수 있다는 걸 새로 배워간다.
문제를 더 많이 풀어봐야 문제에 대한 이해 능력도 늘고, 알고리즘을 짜는 실력도 늘고, 코드를 짜는 실력이 늘텐데
시간이 허락해주지 않는다.
당연히 핑계겠지.
분명 누군가는 나보다 시간이 없더라도 더 많이 풀어보겠지.
그러니까 안일해지지 말자.
