굉장히 오랜만에 포스팅을 하는 것 같습니다. 11월부터 내년 1월까지가 회사에서 가장 바쁜 시기가 될 거라는 말은 장난이 아니었습니다. 그리고 개인적으로 이 문제를 포스팅하기 전 미리 풀어보면서 여러 번 틀리는 것에 '도대체 왜?' 라는 생각을 가지며 끙끙대다가, 정말로 이상한 부분에서 막히고 있었다는 것을 알고 굉장히 허탈했습니다.
문제 자체는 규칙이 많지만 정리하면 꽤 간단해집니다.
1. 페이지 주소는 meta tag 중 property가 og:url 인 곳에 저장된다.
2. 대소문자를 구분하지 않고 단어를 찾아 매칭되는 수 만큼 기본점수
3. <a href="~"> 형태로 걸려 있는 것은 외부링크인데, 이 때 타겟 페이지에는 링크점수를 부여
4. 링크점수 + 기본점수의 합이 가장 큰 페이지, 합이 같은 페이지가 같다면 index가 가장 작은 페이지를 return
하는 문제였습니다. 사실 이 문제를 어렵게 내려면 정말로 어렵게 낼 수 있습니다. 예를 들면 meta tag의 property와 content 등 여러 attribute 들의 순서를 변경한다던지, 단어를 검색할 때 "body" 혹은 "href" 같은 단어로 검색하게 하여 태그에 포함된 문자열이 검색되도록 함정 파기 등등..
하지만 이 문제는 공채 문제임을 감안하면 그렇게 꼬았을 것 같지는 않았다고 생각했고, 역시 주어진 조건을 넘어서는 코너 케이스는 없다는 것이 확인되었습니다. 그럼 풀면 됩니다. meta tag와 링크의 양식은 고정되어 있으므로, string에 저장해놓고 find를 이용하여 index를 얻어냅니다. 단어 역시 find로 찾은 후 양 옆을 체크하는 방법도 있으며, 알파벳이면 스트링에 계속 더하다가, 다른 게 나오면 매칭되는지를 체크하여 찾는 방법도 있습니다.(제가 이 방법으로 풀었습니다. STL을 사용하지 못하는 SW 역량테스트 같은 경우를 대비해서라도 이런 방법을 알아두는 것도 좋을 듯 합니다.)
그리고 저를 며칠간 삽질하게 한 부분.. 매칭 점수는 소수점으로 나올 수 있다는 것이었습니다. 생각해보면 예제에서도 당장 4.5점이라고 나오는데, 저는 우연히 테스트 케이스가 통과되는 int형을 사용하고 있다가 계속 90점에서 삽질을 하였습니다. 언제나 조심해야지 하는 문제이지만 또 겪어버린 문제였습니다.
제 풀이는 소스코드를 클릭하면 볼 수 있습니다.
※해당 소스코드는 참고용이며, 최적화 된 공식 솔루션 소스가 아닙니다. 이 소스를 그대로 복사하여 이용, 또는 제출하는 행위에 대한 불이익은 책임지지 않습니다.
#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
string contentMeta = "<meta property=\"og:url\" content=\"";
string hrefLink = "<a href=\"";
string bodyStart = "<body>";
string bodyEnd = "</body>";
class Score {
public:
double basic, outlink, link;
int idx;
Score() { basic = outlink = link = 0; }
};
string getMetaContent(string &page) {
int pos = page.find(contentMeta) + contentMeta.length();
string ret = "";
while (page[pos] != '"') ret += page[pos++];
return ret;
}
int solution(string word, vector<string> pages) {
map<string, Score> db;
int idx = 0;
transform(word.begin(), word.end(), word.begin(), ::tolower);
for (int i = 0; i < pages.size(); i++) {
transform(pages[i].begin(), pages[i].end(), pages[i].begin(), ::tolower);
}
for (string page : pages) {
string content = getMetaContent(page);
db[content].idx = idx++;
//단어 개수 구하기
int sptr = page.find(bodyStart) + bodyStart.length(), eptr = page.find(bodyEnd);
string chk = "";
for (int i = sptr; i<eptr; i++) {
if (page[i] >= 'a' && page[i] <= 'z') chk += page[i];
else {
if (chk == word) db[content].basic++;
chk = "";
}
}
//외부로 걸린 링크 수
sptr = page.find(bodyStart);
while (1) {
sptr = page.find(hrefLink, sptr);
if (sptr == string::npos) break;
db[content].outlink++;
sptr += hrefLink.length();
}
}
for (string page : pages) {
string content = getMetaContent(page);
//링크 점수
int sptr = page.find(bodyStart);
while (1) {
sptr = page.find(hrefLink, sptr);
if (sptr == string::npos) break;
sptr += hrefLink.length();
string stmp = "";
for (; page[sptr] != '"'; sptr++) stmp += page[sptr];
if (db.find(stmp) != db.end()) {
db[stmp].link += db[content].outlink == 0 ? 0 : db[content].basic / db[content].outlink;
}
}
}
int answer = 0;
double cmp = -1;
for (string page : pages) {
string content = getMetaContent(page);
if (db[content].basic + db[content].link > cmp || (db[content].basic + db[content].link == cmp && answer > db[content].idx)) {
answer = db[content].idx;
cmp = db[content].basic + db[content].link;
}
}
return answer;
}