풀이
[문제 풀이]
이 문제는 어려운 문제는 아니지만 주소를 찾거나 단어를 찾는 과정이 생각보다 까다로웠다.
단어를 구분해 주고, 어떤 부분부터 주소를 나타내는지 찾아주어야 하기 때문이다.
먼저 점수를 계산하기 위해 특정 단어가 몇번 나왔는지 찾는 방법을 알아보자
여기서 중요한 점은 특정 단어는 대소문자 구분을 하지 않는다는 점이다.
그래서 대소문자 구분을 하지 않도록 전부 소문자로 변경을 해주었다.
특정 단어의 경우 알파벳으로만 이루어져 있어야 한다. 만약 abc라는 글자가 찾는 단어일 경우 abcabc인 단어는 내가 찾는 글자가 아니다.
abc@abc인 경우에는 중간에 @가 있으므로 구분된 단어라 abc가 두개 있으므로 2점이 된다.
그래서 알파벳 26자를 set에 넣어두고 만약 알파벳이 set에 있다면, string에 더했다.
만약 알파벳이 아니라면 지금까지 더한 단어가 하나의 단어이므로 word와 일치하는지 검사하고, string을 ""로 초기화했다.
page의 주소와 외부 링크를 찾아야 하는데 찾는 방법은 string의 find함수를 이용했다.
meta의 content를 이용해 page의 주소를 찾고 <a href="를 이용해 외부링크의 주소를 찾아서 구분했다.
특히 외부링크의 경우 여러개가 나올 수 있기 때문에 while을 이용해 몇번째 index부터 탐색할지 증가시켜나갔다.
그리고 찾은 값들은 vector와 map을 이용해 저장했다.
어떤 page에 외부링크가 달려있는지 빠르게 확인하기 위해 [string : int]로 매칭해서 어떤 page에 매칭점수를 더할지 빠르게 찾았다.
이후 매칭점수를 더한 다음 어떤 page의 점수가 가장 높은지 계산해 return했다.
[아이디어 정리]
- 찾는 단어의 대소문자 구분이 없으므로 전부 소문자나 대문자로 바꿔준다.
- 단어는 알파벳으로만 이루어져있기 때문에 다른 문자가 있으면 구분이 된다. 그러므로 find대신 직접 string을 더해가면서 찾는다.
- 이후 string의 find함수를 이용해 page의 주소와 외부링크의 주소를 찾아 저장한다.
- 매칭점수를 계산한 다음 가장 점수가 높은 page를 return한다.
Code
#include <string>
#include <vector>
#include <map>
#include <set>
#include <iostream>
using namespace std;
set<char> alpha={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
int solution(string word, vector<string> pages) {
vector<string>realPages(1);
for (int i=0; i<word.length(); i++)
word[i] = std::tolower(word[i]);
for (int i=0; i<pages.size(); i++)
{
for (int j=0; j<pages[i].length(); j++)
{
pages[i][j] = std::tolower(pages[i][j]);
}
realPages.push_back(pages[i]);
}
vector<float> pScore(pages.size()+1,0);
vector<float> oScore(pages.size()+1,0);
vector<string> myLink(pages.size()+1);
vector<vector<string>> myOtherLink(pages.size()+1);
map<string,int> myMap;
string ss;
string nstr;
for (int i=1; i<realPages.size(); i++)
{
nstr=realPages[i];
ss="<meta property=\"og:url\" content=\"";
int myStLink=nstr.find(ss)+ss.length();
int myEdLink=nstr.find("\"/>",myStLink);
myLink[i]=nstr.substr(myStLink,myEdLink-myStLink);
myMap[myLink[i]]=i;
ss="<a href=\"";
int aStLink=0;
int aEdLink=0;
while(true)
{
aStLink=nstr.find(ss,aEdLink);
aEdLink=nstr.find("\">",aStLink);
if (aStLink==string::npos)
break;
aStLink+=ss.length();
string newStr=nstr.substr(aStLink,aEdLink-aStLink);
myOtherLink[i].push_back(newStr);
}
int BodyLinkSt=nstr.find("<body>");
int BodyLinkEd=nstr.find("</body>");
string wStr="";
for (int j=BodyLinkSt; j<BodyLinkEd; j++)
{
if (alpha.find(nstr[j])==alpha.end())
{
if (wStr==word)
{
pScore[i]+=1;
}
wStr="";
}
else
{
wStr+=nstr[j];
}
}
if (myOtherLink[i].size()>0)
{
oScore[i]=pScore[i]/myOtherLink[i].size();
}
}
for (int i=1; i<realPages.size(); i++)
{
for (int j=0; j<myOtherLink[i].size(); j++)
{
pScore[myMap[myOtherLink[i][j]]]+=oScore[i];
}
}
int retIdx=0;
float maxScore=-1;
for (int i=1; i<realPages.size(); i++)
{
if (maxScore<pScore[i])
{
retIdx=i;
maxScore=pScore[i];
}
}
return retIdx-1;
}
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
'Algorithm > 프로그래머스' 카테고리의 다른 글
| [프로그래머스/C++] 동굴 탐험 (2020 카카오 인턴십) (0) | 2024.03.20 |
|---|---|
| [프로그래머스/C++] 인사고과 (0) | 2024.03.19 |
| [프로그래머스/C++] 호텔 방 배정 (2) | 2024.03.16 |
| [프로그래머스/C++] 공 이동 시뮬레이션 (1) | 2024.03.15 |
| [프로그래머스/C++] 스티커 모으기 (0) | 2024.03.14 |