https://programmers.co.kr/learn/courses/30/lessons/17677
두 개의 문자열에 대해 자카드 유사도를 구하는 문제이다.
자카드 유사도라는 것 자체가 생소했는데,
문제에 자세히 설명이 되어있어서 이해하기에는 어렵지 않았다.
지난 번 프로그래머스 문제를 풀 때
STL을 잘 활용하지 못해서 빙 돌아갔던 게 생각이 나서
이번에는 구현하기 전에 무조건 구글링을 했다!
새삼 C++엔 지원되는 함수가 정말 많은 거 같다
배운 점
1. to_string() 사용 시 주의
- 문자열의 한 글자씩을 가져와서 다중집합의 원소를 만드는 데 그 한 글자를 to_string으로 하게 되면,
string이 나오지 않고 int의 결과값을 얻는다. - string 을 하나 만들어 놓고 += 연산자를 사용하면, int가 아닌 string의 결과를 얻을 수 있다
2. 교집합, 합집합
- <algorithm>의 set_intersection()과 set_union()를 사용하였다
- 위 함수에 사용할 vector들은 사용 전에 sort()를 해주어야 한다
// 교집합
vector<string> intersection(multiSet_A.size() + multiSet_B.size());
auto iter_a = set_intersection(multiSet_A.begin(), multiSet_A.end(), multiSet_B.begin(), multiSet_B.end(), intersection.begin());
intersection.erase(iter_a, intersection.end()); // 남는 공간 비워주기
// 합집합
vector<string> multi_union(multiSet_A.size() + multiSet_B.size());
auto iter_b = set_union(multiSet_A.begin(), multiSet_A.end(), multiSet_B.begin(), multiSet_B.end(), multi_union.begin());
multi_union.erase(iter_b, multi_union.end());3. 벡터 중복 원소 제거
- 다중집합의 교집합이 아닌 일반 교집합에는 중복이 없어야 해서 중복제거를 해주었다
- <algorithm>의 unique() 를 사용하였다
- unique()는 중복되는 원소를 배열의 끝으로 보내고, 그 끝으로 보낸 값의 첫번째 인덱스를 반환한다
- 따라서 erase() 의 첫번째 매개변수로 사용하면 필요없는 원소들을 제거할 수 있다
intersection.erase(unique(intersection.begin(), intersection.end()), intersection.end()); // 교집합 중복 제거4. 특정 원소의 개수 구하기
- <algorithm>의 count() 를 사용하였다
- 아래 코드가 좀 복잡하다.. 원래 매개변수에 때려박는 걸 별로 좋아하진 않는데,
다 풀고나서 프로그래머스에서 다른 분들 코드를 참고해보니까 한 줄이라도 줄이는 거 같아서 저렇게 수정하였다 - count(v.begin(), v.end(), element) : v의 처음부터 끝까지 검사하면서 element의 개수를 구한다
for(iter = intersection.begin(); iter != intersection.end(); iter++)
{
counts_min[idx] = min(count(multiSet_A.begin(), multiSet_A.end(), *iter), count(multiSet_B.begin(), multiSet_B.end(), *iter));
counts_max[idx++] = max(count(multiSet_A.begin(), multiSet_A.end(), *iter), count(multiSet_B.begin(), multiSet_B.end(), *iter));
}문제 정리
구현해야 할 핵심 기능 정리
- 1번에 예외처리 중 달라진 점이 있는데 어떤 문자에 대해 공백, 숫자, 특수문자인지 일일히 검사하는 것보다 그냥 알파벳인지 확인하는 것으로 변경하였다
- 여기서 교집합을 구할 때, 다중집합의 교집합 개념이 조금 다르다고 생각해서
일반 교집합을 만든 후에 다중집합의 교집합을 만들기로 했다. 그랬었다.
아니 근데 여기에서 바보같은 짓을 했다.
문제에서 다중집합에 대한 교집합과 합집합을 설명할 때,
교집합에는 공통원소가 min개 들어가고, 합집합에는 공통원소가 max개 들어간다고 하는데
이건 사실 그냥 교집합과 합집합을 만들면 자연스럽게 되는 거였다 - 그래서 이 문제에서는 사실 교집합을 만들어 중복제거를 할 필요도,
각 다중집합에서 공통원소의 개수를 구하기 위해 count함수를 사용할 필요도 없다 ㅎㅎ;
근데 또 이 방식도 잘 돌아갔다는 것..ㅎ 라이브러리 공부했다고 치고, 코드 정리도 좀 했다구 생각해야지..
CODE
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
#define MUL 65536
int solution(string str1, string str2) {
vector<string> multiSet_A;
vector<string> multiSet_B;
vector<string> ::iterator iter;
for(int i=0; i<str1.length()-1; i++)
{
string tmp;
if(isalpha(str1[i]) && isalpha(str1[i+1]))
{
tmp += tolower(str1[i]);
tmp += tolower(str1[i+1]);
multiSet_A.push_back(tmp);
}
}
for(int i=0; i<str2.length()-1; i++)
{
string tmp;
if(isalpha(str2[i]) && isalpha(str2[i+1]))
{
tmp += tolower(str2[i]);
tmp += tolower(str2[i+1]);
multiSet_B.push_back(tmp);
}
}
if(multiSet_A.size() == 0 && multiSet_B.size() == 0) // 다중집합 A, B가 모두 공집합인 경우
{
return MUL;
}
sort(multiSet_A.begin(), multiSet_A.end());
sort(multiSet_B.begin(), multiSet_B.end());
vector<string> intersection(multiSet_A.size() + multiSet_B.size());
auto iter_a = set_intersection(multiSet_A.begin(), multiSet_A.end(), multiSet_B.begin(), multiSet_B.end(), intersection.begin());
intersection.erase(iter_a, intersection.end()); // 남는 공간 비워주기
// 다중집합의 합집합
vector<string> multi_union(multiSet_A.size() + multiSet_B.size());
auto iter_b = set_union(multiSet_A.begin(), multiSet_A.end(), multiSet_B.begin(), multiSet_B.end(), multi_union.begin());
multi_union.erase(iter_b, multi_union.end());
int Jaccard = 0;
Jaccard = ((float)intersection.size() / (float)multi_union.size()) * 65536;
cout<<Jaccard<<endl;
return Jaccard;
}CODE (바보버전..)
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
#define MUL 65536
int solution(string str1, string str2) {
vector<string> multiSet_A;
vector<string> multiSet_B;
vector<string> ::iterator iter;
for(int i=0; i<str1.length()-1; i++)
{
string tmp;
if(isalpha(str1[i]) && isalpha(str1[i+1]))
{
tmp += tolower(str1[i]);
tmp += tolower(str1[i+1]);
multiSet_A.push_back(tmp);
}
}
for(int i=0; i<str2.length()-1; i++)
{
string tmp;
if(isalpha(str2[i]) && isalpha(str2[i+1]))
{
tmp += tolower(str2[i]);
tmp += tolower(str2[i+1]);
multiSet_B.push_back(tmp);
}
}
if(multiSet_A.size() == 0 && multiSet_B.size() == 0) // 다중집합 A, B가 모두 공집합인 경우
{
return MUL;
}
sort(multiSet_A.begin(), multiSet_A.end());
sort(multiSet_B.begin(), multiSet_B.end());
// 일반 교집합
vector<string> intersection(multiSet_A.size() + multiSet_B.size());
auto iter_a = set_intersection(multiSet_A.begin(), multiSet_A.end(), multiSet_B.begin(), multiSet_B.end(), intersection.begin());
intersection.erase(iter_a, intersection.end()); // 남는 공간 비워주기
//-----------------------이 부분이 전혀 필요가 없음-------------------------
intersection.erase(unique(intersection.begin(), intersection.end()), intersection.end()); // 교집합 중복 제거
// 교집합 내 원소의 최소/최대 개수
int counts_min[intersection.size()];
int counts_max[intersection.size()];
int idx = 0;
for(iter = intersection.begin(); iter != intersection.end(); iter++)
{
counts_min[idx] = min(count(multiSet_A.begin(), multiSet_A.end(), *iter), count(multiSet_B.begin(), multiSet_B.end(), *iter));
counts_max[idx++] = max(count(multiSet_A.begin(), multiSet_A.end(), *iter), count(multiSet_B.begin(), multiSet_B.end(), *iter));
}
// 다중집합의 교집합
vector<string> multi_intersection;
idx = 0;
for(iter = intersection.begin(); iter!= intersection.end(); iter++)
{
for(int i=0; i<counts_min[idx]; i++)
{
multi_intersection.push_back(*iter);
}
idx++;
}
//-----------------------------------------------------------------------
// 다중집합의 합집합
vector<string> multi_union(multiSet_A.size() + multiSet_B.size());
auto iter_b = set_union(multiSet_A.begin(), multiSet_A.end(), multiSet_B.begin(), multiSet_B.end(), multi_union.begin());
multi_union.erase(iter_b, multi_union.end());
// 자카드 유사도 계산
int Jaccard = 0;
Jaccard = ((float)multi_intersection.size() / (float)multi_union.size()) * 65536;
return Jaccard;
}
Game Programmer