2019 KAKAO BLIND RECRUITMENT - 매칭 점수

모든 문제는 C++로 구현되어 있습니다.

 

이 문제는 세 단계로 나눠서 생각할 수 있다.

---

1. <meta> 태그에서 페이지의 링크를 구하고, 이를 기본 점수 및 최종 점수를 저장하는 맵에 매핑시키기

2. 페이지 별 기본점수 구하기

3. 각 페이지의 외부 링크를 구하고, 이에 맞게 링크 점수 뿌려주기

---

1. <meta> 태그에서 페이지의 url을 구하고, 이를 기본 점수 및 최종 점수를 저장하는 맵에 매핑시키기

•   먼저 <sstream> 헤더에 있는 std::stringstream을 사용해서 공백을 기준으로 각 페이지의 단어를 나눠서 별도의 배열 wordList에 저장한다. 그 다음 wordList를 순회하면서 "<meta"로 시작하는 단어를 찾고, 이 단어 이후로 처음 나타나는 맨 끝 단어가 '>'인 단어를 찾는다.
• 이 단어에서 "content=" 이하의 문자열을 뽑아내면 페이지 url을 찾을 수 있고, 이 값을 미리 생성해놓은 기본 점수와 최종 점수를 저장할 2개의 맵에 저장한다. 저장할 때 페이지 url을 키로 하고, 값은 0으로 설정해준다.

2. 페이지 별 기본점수 구하기

• KMP 알고리즘을 사용하여 페이지에서 주어진 문자열 word를 찾아 갯수를 센다. 이때 word 앞, 뒤의 문자가 알파벳인지 확인하고, 알파벳이면 단어로 구분되지 않으므로 갯수에 더하지 않고 패스한다. 이렇게 구한 값은 기본 점수를 저장하는 맵에 저장한다. 
• KMP 알고리즘은 아래와 같이 구현할 수 있다.

 

//KMP failure function
vector<int> getFailure(const string& str) {
	int i, j = 0, len = str.length();
	vector<int> ret(len, 0);
	for (i = 1; i < len; i++) {
		while (j > 0 && str[i] != str[j]) j = ret[j - 1];
		if (str[i] == str[j]) ret[i] = ++j;
	}
	return ret;
}

//KMP
vector<int> kmp(const string & a, const string & b, vector<int> failure) { // a 안에서 b를 찾고, 그 시작 지점의 인덱스를 저장한 배열을 리턴한다.

	vector<int> ret;
	int i, j = 0, aLen = a.length(), bLen = b.length();
	for (i = 0; i < aLen; i++) {
		while (j > 0 && a[i] != b[j]) j = failure[j - 1];
		if (a[i] == b[j]) {
			if (j == bLen - 1) {
				ret.push_back(i - bLen + 1);
				j = failure[j];
			}
			else ++j;
		}
	}
	return ret;
}

 

 

3. 각 페이지의 외부 링크를 구하고, 이에 맞게 링크 점수 뿌려주기

• 단계 1에서 구해놓은 wordList 배열을 이용하여 "href="로 시작하는 단어를 찾고, 이 단어에서 외부 링크를 뽑아낸다.
• 주의할 점은, <a> 태그 이외에 다른 태그에도 href 속성이 붙을 수 있다. 따라서 찾은 단어의 바로 앞 단어에서 끝에 두 글자가 "<a" 인지 확인해줘야 한다. 이것때문에 시간을 참 많이 소비했다.     
• 이렇게 구한 외부 링크의 갯수를 확인하고, 현재 페이지의 기본점수를 갯수로 나눠서 외부 링크로 연결된 페이지에 전부 뿌려주면 된다. 기본점수는 미리 설정해놓은 맵에서 꺼내쓰면 된다.

 

이렇게 각 페이지의 최종 점수를 모두 구하면 <페이지 번호, 최종 점수> 쌍을 저장하는 배열을 만들고, 이 배열을 정렬한다. 그러면 정렬된 배열의 첫 번째 원소의 페이지 번호가 우리가 구하려고 하는 답이 된다.

 

 

구현 자체가 어려운 문제는 아니었지만, 문자열 처리와 예외 처리에서 시간을 많이 잡아먹는 문제였다. 문자열 처리에 관한 문제를 좀 더 풀어봐서 익숙해질 수 있도록 노력해야겠다.

 

//KMP failure function
vector<int> getFailure(const string& str) {
	int i, j = 0, len = str.length();
	vector<int> ret(len, 0);
	for (i = 1; i < len; i++) {
		while (j > 0 && str[i] != str[j]) j = ret[j - 1];
		if (str[i] == str[j]) ret[i] = ++j;
	}
	return ret;
}

//KMP
vector<int> kmp(const string & a, const string & b, vector<int> failure) { // a 안에서 b를 찾고, 그 시작 지점의 인덱스를 저장한 배열을 리턴한다.

	vector<int> ret;
	int i, j = 0, aLen = a.length(), bLen = b.length();
	for (i = 0; i < aLen; i++) {
		while (j > 0 && a[i] != b[j]) j = failure[j - 1];
		if (a[i] == b[j]) {
			if (j == bLen - 1) {
				ret.push_back(i - bLen + 1);
				j = failure[j];
			}
			else ++j;
		}
	}
	return ret;
}

void toLowerCase(string & str) { // 대문자 -> 소문자로 변환
	for (auto& ch : str) {
		if (ch >= 'A' && ch <= 'Z') ch = ch - 'A' + 'a';
	}
}

bool isAlphabet(char ch) {
	return ch >= 'a' && ch <= 'z';
}

bool cmp(pair<int, double> a, pair<int, double> b) {
	if (a.second == b.second) return a.first < b.first;
	return a.second > b.second;
}

//모든 page 및 word의 단어는 소문자로 변환한다.
int solution(string word, vector<string> pages) {
	int i, idx = 0, wLen = word.length();
	toLowerCase(word);
	unordered_map<string, double> base, totalScore;
	vector<string> urlList;
	vector<string>* pageWordList = new vector<string>[pages.size()]; //각 페이지의 단어들이 저장되는 배열

	// 1. 링크 구해서 매핑하기
	for (auto page : pages) {
		stringstream ss(page);
		string tmp;
		vector<string>& wordList = pageWordList[idx];
		while (ss >> tmp) {
			wordList.push_back(tmp);
		}

		for (i = 0; i < wordList.size(); i++) {
			if (wordList[i] == "<meta") {
				while (wordList[i][wordList[i].length() - 1] != '>') i++;
				if (wordList[i].substr(0, 7) == "content") {
					int idx = 9, urlLen = 1;
					while (wordList[i][idx] != '"') {
						idx++;
						urlLen++;
					}

					string url = wordList[i].substr(8, urlLen + 1);
					totalScore[url] = 0.0;
					base[url] = 0.0;
					urlList.push_back(url);
				}
			}
		}
		idx++;
	}

	idx = 0;
	//2. 페이지별 기본점수 구하기
	for (auto page : pages) {
		int pLen = page.length(), baseScore = 0;
		toLowerCase(page);

		//2-1. KMP 알고리즘을 이용해 기본 점수 구하기
		vector<int> failure = getFailure(word);
		vector<int> kmpVec = kmp(page, word, failure);
		for (auto idx : kmpVec) {
			if ((idx > 0 && isAlphabet(page[idx - 1])) || ((idx + wLen < pLen) && isAlphabet(page[idx + wLen]))) { // not word
				continue;
			}
			baseScore++;
		}
		base[urlList[idx]] = baseScore;
		idx++;
	}


	for (auto it : urlList) {
		totalScore[it] = base[it];
	}
	idx = 0;

	//3. 외부 링크 구하고, 점수 뿌려주기
	for (auto page : pages) {
		vector<string>& wordList = pageWordList[idx], outLinkList;
		for (i = 0; i < wordList.size(); i++) {
			if (wordList[i].size() > 5 && wordList[i].substr(0, 5) == "href=") { //href
				if (wordList[i - 1].substr(wordList[i - 1].length() - 2, 2) != "<a") continue;
				//"href="가 a 태그가 아닌 다른 태그에 들어있을 경우 패스
				int idx = 6, urlLen = 1;
				while (wordList[i][idx] != '"') {
					idx++;
					urlLen++;
				}
				string outLink = wordList[i].substr(5, urlLen + 1);
				outLinkList.push_back(outLink);
			}
		}
		double outScore = base[urlList[idx]] * 1.0 / outLinkList.size();

		for (auto out : outLinkList) {
			totalScore[out] += outScore;
		}
		idx++;
	}

	vector<pair<int, double>> rank;
	for (i = 0; i < urlList.size(); i++) {
		string url = urlList[i];
		rank.emplace_back(i, totalScore[url]);
	}

	sort(rank.begin(), rank.end(), cmp);
	int answer = rank[0].first;
	return answer;
}