[2019 카카오] 매칭 점수

programmers.co.kr/learn/courses/30/lessons/42893

코딩테스트 연습 - 매칭 점수

#include <string>
#include <vector>
#include <unordered_map>
#include <cctype>

using namespace std;

void str_tolower(string &str) {
	for (auto it = str.begin(); it != str.end(); it++) {
		(*it) = tolower(*it);
	}
}

bool is_alpha(char c) {
	return (c > 'a' && c < 'z') || (c > 'A' && c < 'Z');
}

int solution(string word, vector<string> pages) {
	int basic[20] = { 0 }, outlink[20] = { 0 };
	double matching[20] = { 0 }, link[20] = { 0 };
	vector<int> my_link[20];
	int n = pages.size();

	// map 만들기(url, index)
	unordered_map<string, int> urls;
	string meta_tag = "<meta property=\"og:url\" content=\"";

	for (int i = 0; i < n; i++) {
		int start = pages[i].find(meta_tag);
		int end = pages[i].find("\"/>", start);
		string url = pages[i].substr(start + meta_tag.length(), end - start - meta_tag.length());
		urls.insert({ url, i });
	}

	//// 외부 링크 찾기
	string a_tag = "<a href=\"";

	for (int i = 0; i < n; i++) {
		int start = pages[i].find(a_tag, 0);
		while (start >= 0) {
			int end = pages[i].find("\">", start);
			string url = pages[i].substr(start + a_tag.length(), end - start - a_tag.length());

			start = pages[i].find(a_tag, start + 1);

			// my_link, outlink 업데이트
			outlink[i]++;
			if (urls.find(url) != urls.end()) {
				my_link[urls[url]].push_back(i);
			}
		}
	}

	// 기본점수 구하기
	str_tolower(word);
	
	for (int i = 0; i < n; i++) {
		str_tolower(pages[i]);

		int start = pages[i].find(word, 0);
		while (start >= 0) {
			char c1 = pages[i].at(start - 1);
			char c2 = pages[i].at(start + word.length());

			start = pages[i].find(word, start + 1);

			if (!is_alpha(c1) && !is_alpha(c2)) basic[i]++;
		}
	}

	// 링크점수 구하기
	for (int i = 0; i < n; i++) {
		// 나한테 링크가 걸린애들의 점수 더하기
		for (int m : my_link[i]) {
			link[i] += (double) basic[m] / outlink[m];
		}
	}

	// 매칭점수 구하기
	for (int i = 0; i < n; i++) {
		matching[i] = basic[i] + link[i];
	}

	// 가장 높은 점수 구하기
	int answer = 0;
	for (int i = 1; i < n; i++) {
		if (matching[i] > matching[answer]) answer = i;
	}

	return answer;
}

 

문제가 굉장히 긴 것에 비해 별로 어려운 것 없고 시키는대로만 잘 풀면 되는 문제

C++ 문자열처리가 매우 불편하다는 것을 다시 한 번 깨달았다.

나도 서브로 파이썬을 파야겠다...T.T