Java) 프로그래머스 - 뉴스 클러스터링
문제 링크
문제
-
여러 언론사에서 쏟아지는 뉴스, 특히 속보성 뉴스를 보면 비슷비슷한 제목의 기사가 많아 정작 필요한 기사를 찾기가 어렵다. 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”는 같은 원소로 취급한다.
출력 형식
- 입력으로 들어온 두 문자열의 자카드 유사도를 출력한다. 유사도 값은 0에서 1 사이의 실수이므로, 이를 다루기 쉽도록 65536을 곱한 후에 소수점 아래를 버리고 정수부만 출력한다.
👀 풀이
-
이틀에 걸쳐 푼 문제… 수학적 지식이 부족해서인가?ㅠㅠ 그래도 답지를 보지 않고 질문게시판의 힌트들만 참고해서 풀었기 때문에 많이 그동안에 비하면 발전한 것 같다…ㅎ
-
이 문제를 풀려면 문제의 조건에 맞는 교집합과 합집합만 잘~ 구하면 된다. 문제가 길어서 처음에는 어렵게 느껴지는 경향이 있는데 한 문장씩 차근차근 읽어보면 교집합과 합집합을 구하는 알고리즘 자체는 어렵지 않게 떠올릴 수 있었다. 문제라면 엣지케이스를 생각하지 못했다는 것…
교집합 구하기
- 단순하게
for (String s : 2글자씩 자른 문자열 배열2) {
2글자씩 자른 문자열 배열1.contains(s);
}
이렇게 가면 제대로 된 교집합을 구할 수 없다. 각종 엣지 케이스에 걸려서 통과할 수 없다.
- 예를 들어
BAAAA,AAA와 같은 경우에는 각각{"BA", "AA", "AA", "AA"}와{"AA", "AA"}를 얻을 수 있다. -
정확한 교집합은
{"AA", "AA"}이지만 위와 같은 로직으로 교집합을 구하게 되면{"AA", "AA", "AA"}라는 결과를 얻게 된다.(내가 그랬음) 그래서 여기부터 틀리기 때문에 정답을 구할 수가 없는 것이다. - 그래서 해시맵을 사용해 각 배열의 문자열 출현횟수를 센 다음 두 맵에 공통으로 존재하는 문자열의 출현횟수 중 더 적은 횟수만큼 교집합 배열에 추가해 주는 방식으로 알고리즘을 작성했다.
합집합 구하기
-
두 집합을 그냥 더한 값으로 구하면 안된다.
A = {1, 1, 1},B = {1, 1, 1, 1}과 같은 두 집합이 존재하면 이 두 집합의 합집합은{1, 1, 1, 1}이 되어야 한다.(모르겠으면 문제 참고) 그런데 단순하게 더하면 1이 7개 들어간 집합이 된다. - 그래서
A + B단순하게 더한 합집합을 구한 다음 교집합의 원소를 빼 주었다. 도식으로 나타내면A + B - 교집합 - 코드로는
remove(obj)메서드를 사용해 교집합에 존재하는 모든 원소를 제거하도록 했다.remove(obj)는 배열에 매개변수와 일치하는 여러 값 중 가장 빠른 인덱스의 원소 하나만을 제거하기 때문에 교집합을 정확하게 제거할 수 있다.
자카드 유사도 구하기
- 위에서 구한 교집합과 합집합의 배열 길이를 이용해서 구할 수 있다. 이 때 길이는 정수형으로 얻게 된다.
- 여기도 은근 까다로운데… 최종 리턴타입은 정수형인데 문제가 시키는대로 하면 중간 연산 결과는 실수형으로 얻게 된다.
- 일단 자바에서는 정확하게 타입캐스팅을 해 주어야 정확한 값을 얻을 수 있기 때문에 교집합과 합집합의 길이를 실수형으로 타입캐스팅을 먼저 한 다음에 나누기 연산을 수행하야 한다.(안 그러면 0만 나옴)
-
그 다음 65536을 곱해주고
Math.floor(double)메서드로 소수점을 버리면 된다. - 이 때 또 예외사항으로는 0/0과 같이 0으로 나누게 되는 경우가 있다. 0으로 나누는 경우는 바로
Arithmetic exeption이 뜰테니 쉽게 찾을 수 있지만(이것도 경험함) 0/2 처럼 교집합은 없는데 합집합은 있는 경우는 결과값으로 0이 나오기 때문에 쉽게 찾기가 힘들다.(여기에 걸려서 테스트 케이스 5, 13을 통과 못했음) - 그래서 교집합과 합집합의 합이 0일 때에만 1로 정의하면(혹은 65536으로 바로 해도 됨) 0/2와 같은 케이스를 통과할 수 있다.
자기 성찰
- 통과 후 다른 사람들의 코드를 보니 스트림을 잘 사용하신 분이 계셨다. 아직은 배열을 순회해야 하면 무지성으로 for문을 쓰고 보는데 내일 스트림을 사용한 코드를 참고해서 리팩토링을 해 보아야 겠다. 항상 맘속에만 스트림을 담아두고 정작 익숙하지 않다고 안 쓰니까 계속 안 쓰게 된다!