문제 링크 : programmers.co.kr/learn/courses/30/lessons/42893
<전체적인 알고리즘>
파씽 능력과 자료구조 사용 능력을 알아보기 위한 문제로 보여진다.
자신의 url , 외부링크 url , 일치 단어 개수를 찾는 문제이다. 문자열을 파씽해서 값을 얻을 수 있다.
웹페이지 개수가 최대 20개 밖에 되지 않으니 배열에 넣어서 저장하여도 시간복잡도에 크게 영향을 주지 않는다. 하지만 페이지 개수가 많아지면 map을 사용하여야 하니 연습삼아 map으로 구현하였다.
부가적인 설명은 코드 주석에 달아 놓았다.
<전체 코드>
#include<iostream>
#include <string>
#include <vector>
#include<map>
using namespace std;
class info
{
public:
int index, base_score;
vector<string> other_link;
info() {}
info(int index, int base_score, vector<string> &other_link)
{
this->index = index;
this->base_score = base_score;
this->other_link = other_link;
}
};
string word="";
vector<string> pages;
map<string,info> mp;
map<string, info>::iterator iter;
double total_score[22];
string find_this_url(string page) //해당 url 찾아서 반환
{
int index = page.find("<meta property=")+33; //url 시작부분 찾기
string url = "";
for (int i = index; page[i] != '"'; i++)
{
url += page[i];
}
return url;
}
vector<string> find_other_url(string page) //외부 링크 url들 찾아서 반환
{
vector<string> v;
int start_index = 0;
while (1)
{
int index = page.find("<a href=",start_index)+9; //url시작부분 찾기
if (index == 8)break; //못찾으면 탈출
string url = "";
for (; page[index] != '"'; index++)
{
url += page[index];
}
v.push_back(url);
start_index = page.find("</a>", index)+4;
}
return v;
}
int base_score(string page) //기본 점수 구해서 반환
{
for (int i = 0; i < page.size(); i++)page[i] = tolower(page[i]); //소문자로 전부 변환
int index = page.find("<body>") + 7;
int ws = word.size();
int score = 0;
while (1)
{
index = page.find(word, index); //target 단어 찾기
if (index == -1)break; //없으면 탈출
if (!(page[index - 1] >= 'a'&&page[index - 1] <= 'z') && !(page[index - 1] >= 'A'&&page[index - 1] <= 'Z'))
{
if (!(page[index + ws] >= 'a'&&page[index + ws] <= 'z') && !(page[index + ws] >= 'A'&&page[index + ws] <= 'Z'))
{
score++; //앞 뒤가 영어문자가 아니면 단어임
}
}
index += ws;
}
return score;
}
int solution(string words, vector<string> pages2) {
pages = pages2;
word=words;
for (int i = 0; i < word.size(); i++)word[i] = tolower(word[i]);
for (int i = 0; i < pages.size(); i++)
{
string url=find_this_url(pages[i]); //자신의 url찾기
vector<string> v = find_other_url(pages[i]); //외부 링크 url들 찾기
int score = base_score(pages[i]); //기본 점수 구하기
mp.insert(make_pair(url, info(i, score,v))); //map에 넣어주기
}
for (iter = mp.begin(); iter != mp.end(); iter++)
{
int index = iter->second.index;
int base_score = iter->second.base_score;
total_score[index] += base_score; //자신의 점수에 기본 점수 더해주기
vector<string> other_link = iter->second.other_link;
for (int i = 0; i < other_link.size(); i++) //외부 링크들 링크 점수 더해주기
{
map<string, info>::iterator iter2;
string url = other_link[i];
iter2 = mp.find(url);
if (iter2 == mp.end())continue; //외부링크가 pages에 없으면 스킵
int index2 = iter2->second.index;
if(other_link.size()>0)
total_score[index2] +=(double) base_score / other_link.size();
}
}
double maxx = 0;
int result = 0;
for (int i = 0; i < pages.size(); i++)
{
if (maxx < total_score[i])
{
maxx = total_score[i];
result = i;
}
}
return result;
}
궁금하신 점은 댓글에 남겨주시면 답변드리겠습니다.
반응형
'프로그래머스 코딩 문제 > 카카오 기출문제' 카테고리의 다른 글
| [프로그래머스] 보석 쇼핑 (2020 카카오 인턴십) (0) | 2020.11.01 |
|---|---|
| [프로그래머스] 방금그곡 (2018 KAKAO BLIND RECRUITMENT) (0) | 2020.09.10 |
| [프로그래머스] 기둥과 보 설치 (2020 KAKAO BLIND RECRUITMENT) (level 3) (0) | 2020.09.03 |
| [프로그래머스] 오픈채팅방 (2019 KAKAO BLIND RECRUITMENT) (0) | 2020.09.02 |
| [프로그래머스] 프렌즈4블록 (2018 KAKAO BLIND RECRUITMENT) (0) | 2020.08.31 |