[C++] 프로그래머스 2019 KAKAO BLIND RECRUITMENT 매칭 점수

코딩테스트/코딩테스트 연습 2020. 10. 28. 09:29

728x90

(거의 4시간..?)

정답률 6%문제라는데 솔직히 어렵다기보단 고려해야 될 경우가 많고 다양한 문자열 처리를 할 수 있어야 풀 수 있는 문제. 이걸 어떻게 시간 내에 풀라나ㅋㅋ

C++로 문자열 처리하는게 진짜 불편하다는걸 깨닫게 해줬다. C++로 소문자 변환 처음 써본듯

그리고 검색어가 <body> 파트에서 찾는지 문자열 전체에서 찾는지 설명이 불친절하다. (body에서만 찾아도 된다.)

아이디어는 결국

1. 소문자 대문자 구분 없이 검색이 되야하니까 word와 pages를 모두 소문자 변환시킨다

2. 각 page가 가지고 있는 url를 찾아서 저장한다.

3. 각 page가 가지고 있는 외부 링크를 찾아 저장한다.

4. 각 page가 가지고 있는 텍스트와 검색어를 비교해 기본 점수 저장한다.

5. 각 인덱스가 가지고 있는 기본점수와 외부 링크 점수를 계산해 매칭점수를 만든다.

6. 매칭 점수를 정렬해서 정답을 구한다.

이 과정에서 string 전체를 순회하며 특정 문자열 모두 찾기, string 토큰화 과정 등 문자열을 다양하게 활용해야 된다.

다 풀었는데 테스트케이스 9, 10이 틀려서 별 짓을 다해도 못찼았는데

(9번 오류) url를 검색할 때 "content=\"https://" 이것만 검색하면 오류나고 "<meta property=\"og:url\" content=\"https://" 이걸 통채로 검사해야된다.

(10번 오류) 외부 링크 검색할 때 "href=\"https://"하면 오류나고 "<a href=\"https://"를 써줘야 통과한다.

#include <vector>
#include <algorithm>
#include <map>
#include <sstream>
#include <string>

using namespace std;

// 알파벳이 아닌 경우
bool wordChange(char c) {
	return c == '\'' || !isalpha(c);
}

// first는 내림차순 second는 오름차순
bool comp(pair<double, int> a, pair<double, int> b) {
	if (a.first == b.first) return a.second < b.second;
	return a.first > b.first;
}

int solution(string word, vector<string> pages) {
	// word 소문자로 치환
	transform(word.begin(), word.end(), word.begin(), ::tolower); // ::이거 안써주면 프로그래머스에서 오류남

	// url이름과 그에 맞는 index 저장
	map<string, int> urlName;
	// 각 index가 가지고 있는 url 링크 저장
	vector<vector<string>> links;
	// 각 index가 가지고 있는 기본 점수
	vector<int> basicScore;
    // 매칭 점수와 인덱스
	vector<pair<double, int>> matchScore;

	for (int i = 0; i < pages.size(); i++) {
		// 웹페이지 소문자 치환
		transform(pages[i].begin(), pages[i].end(), pages[i].begin(), ::tolower);

		// 웹페이지 url 알아내고 저장
		string content = "<meta property=\"og:url\" content=\"https://";
		int contentPos = pages[i].find(content);
		int contentStart = contentPos + content.size();
		int contentEnd = pages[i].substr(contentStart).find("\"/>");
		urlName[pages[i].substr(contentStart, contentEnd)] = i + 1;

		// body 파트 분리
		int bodyStartIdx = pages[i].find("<body>");
		int bodyEndIdx = pages[i].find("</body>");
		string bodyPage = pages[i].substr(bodyStartIdx, bodyEndIdx - bodyStartIdx);

		// 외부 링크 탐색
		vector<string> link;
		string href = "<a href=\"https://";
		int hrefPos = bodyPage.find(href);
		while (hrefPos != std::string::npos)
		{
			int hrefStart = hrefPos + href.size();
			int hrefEnd = bodyPage.substr(hrefStart).find("\">");
			link.push_back(bodyPage.substr(hrefStart, hrefEnd));
			hrefPos = bodyPage.find(href, hrefStart + hrefEnd);
		}

		// index가 가진 외부 링크 저장
		links.push_back(link);

		// 특수 문자들도 분리하기 위해 알파벳이 아닐시 싹다 공백으로 변환
		replace_if(bodyPage.begin(), bodyPage.end(), wordChange, ' ');

		// body 파트에서 검색어와 비교해 기본 점수 저장
		int score = 0;
		istringstream iss(bodyPage);
		string token;
		while (getline(iss, token, ' ')) {
			if (word.compare(token) == 0)
				score++;
		}
		basicScore.push_back(score);
	}
    
    // 각 인덱스에 기본 점수를 넣어준다
	for (int i = 0; i < links.size(); i++) {
		matchScore.push_back(make_pair(basicScore[i], i));
	}
    
    // 각 인덱스에 링크 점수를 추가한다
	for (int i = 0; i < links.size(); i++) {
		int linkSize = links[i].size();
		for (int j = 0; j < linkSize; j++) {
            // url이 존재할 경우에만 계산
			if (urlName[links[i][j]] != 0) {
				matchScore[urlName[links[i][j]] - 1].first += (double)basicScore[i] / (double)linkSize;
			}
		}
		
	}
    
    // 매칭 점수를 정렬한다(점수는 내림차순으로 인덱스는 오름차순으로)
	sort(matchScore.begin(), matchScore.end(), comp);
    
    // 매칭점수가 제일 높은 것들 중 인덱스가 가장 작은 경우
	return matchScore[0].second;
}

728x90

저작자표시

'코딩테스트 > 코딩테스트 연습' 카테고리의 다른 글

[C++] 삼성 1868. 파핑파핑 지뢰찾기 (0)	2020.10.28
[C++] 삼성 1210. [S/W 문제해결 기본] 2일차 - Ladder1 (0)	2020.10.28
[C++] 프로그래머스 2018 KAKAO BLIND RECRUITMENT [1차] 셔틀버스 (0)	2020.10.28
[C++] 프로그래머스 2020 KAKAO BLIND RECRUITMENT 블록 이동하기 (0)	2020.10.28
[C++] 프로그래머스 2018 KAKAO BLIND RECRUITMENT [1차] 추석 트래픽 (0)	2020.10.28

ABOUT ME

🤔메모장😦 🤔메모장😦

'코딩테스트 > 코딩테스트 연습' 카테고리의 다른 글

티스토리툴바

ABOUT ME

'코딩테스트 > 코딩테스트 연습' 카테고리의 다른 글

관련글 관련글 더보기

티스토리툴바