반응형
해당 문제는 프로그래머스 코딩테스트 연습에 있는 문제입니다.
아래 링크를 통해 풀 수 있습니다.
https://programmers.co.kr/learn/courses/30/lessons/42893
문제가 상당히 길고 해답 코드도 상당히 깁니다.
문자열을 잘 처리해야 하는 문제이며 각 페이지마다 점수를 구하는 것도 중요합니다.
여기서 주의해야할 점은 다음과 같습니다.
1. 문제가 제시하고있는 조건을 무조건 만족 시킬 것.(가장 중요)
2. 페이지 주소와 해당 페이지와 링크된 주소들을 구한 후 점수를 어떤식으로 뿌려줄 것인가?
3. 기본점수(문자열)을 구할 때 대소문자를 구별하지 않는다.
이 문제의 조건을 보면 다음과 같습니다.
해당 페이지의 url은 <meta>데이터로 주어진다.
즉, 아무 url을 찾으면 안되고 <meta>데이터 안에 있는 url을 찾아야 합니다.
외부 링크 또한 "<a href=" 구조로 되어 있으며 url은 무조건 https://로 시작한다는 점입니다.
따라서 해당 조건을 찾기위한 문자열은 친절하게도 page예시문에 제시하고 있습니다.
<meta charset=\"utf-8\">\n <meta property=\"og:url\" content=\"https://careers.kakao.com/interview/list\"/>\n</head> 이런식으로 말이죠.....
저는 점수를 구하기 위해 unordered_map 2개를 사용했고 추가로
vector에 각 페이지별 index정보를 담아 마지막에 처리해 줬습니다.
생각보다 많이 까다로운 문제였습니다.
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
unordered_map<string, pair<double, double>> link_score;
unordered_map<string, vector<string>> a_hrefList;
int find_string(const char * word, const string&s, int index){
if(*word == '\0'){
if((s[index] < 'A' || s[index] > 'Z') && (s[index] < 'a' || s[index] > 'z') ){
return index;
} return 0;
}
if(*word == tolower(s[index]))
return find_string(word + 1, s, index + 1);
else
return 0;
}
int find_meta(const string& s){
for(int i = 0; i < s.size(); i++){
int flag = 0;
if(s[i] == '<'){
if((flag = find_string("<meta property=\"og:url\" content=\"https:/", s, i))){
return flag;
}
}
}
return 0;
}
string content_init(const string&s, int& index){
string temp = ""; index++;
for(; index < s.size(); index++){
if(s[index] == '\"')
return temp;
else
temp += s[index];
}
return "";
}
int body_line(const string& body, const string& s, int index){
for(int i = index; i < s.size(); i++){
int flag = 0;
if(body[0] == s[i]){
if((flag = find_string(body.c_str(), s, i))){
return flag;
}
}
}
return 0;
}
void link_n_word(const string& word, const string& s, int index, const string& my_link, const int& n){
int link_point = 0, word_point = 0, j = 0;
for(int i = index; i < s.size(); i++){
int flag = 0;
if(word[0] == tolower(s[i])){
if((s[i - 1] < 'A' || s[i - 1] > 'Z') && (s[i - 1] < 'a' || s[i - 1] > 'z' )){
if((flag = find_string(word.c_str(), s, i))){
word_point++; i = flag;
}
}
}else if('<' == s[i]){
if((flag = find_string("<a href=\"https:/", s, i))){
string link_cp = "";
i = flag + 1;
while(s[i] != '\"'){ link_cp += s[i]; i++;}
link_point++;
a_hrefList[my_link].emplace_back(link_cp);
}
}
}
link_score[my_link].first = (double)word_point;
link_score[my_link].second = (double)word_point / (double)link_point;
}
int solution(string word, vector<string> pages) {
int answer = 0;
vector<string> webList;
for(int i = 0; i < word.size(); i++)
word[i] = tolower(word[i]);
for(int i = 0; i < pages.size(); i++){
int meta = find_meta(pages[i]);
string my_link = content_init(pages[i], meta);
webList.emplace_back(my_link);
int index = body_line("<body>", pages[i], meta);
link_n_word(word, pages[i], index, my_link, i);
}
for(int i = 0; i < webList.size(); i++){
for(int j = 0; j < a_hrefList[webList[i]].size(); j++){
string s = a_hrefList[webList[i]][j];
link_score[s].first += link_score[webList[i]].second;
}
}
double score_max = link_score[webList[0]].first;
for(int i = 1; i < webList.size(); i++){
if(score_max < link_score[webList[i]].first){
score_max = link_score[webList[i]].first;
answer = i;
}
}
return answer;
}
반응형
'코딩테스트 > 프로그래머스' 카테고리의 다른 글
| 프로그래머스] C++ 2019 KAKAO BLIND RECRUITMENT - 오픈 채팅방(Level 1) (0) | 2020.05.09 |
|---|---|
| 프로그래머스] C++ 2018 KAKAO BLIND RECRUITMENT - 방금그곡(Level 2) (0) | 2020.05.08 |
| 프로그래머스] C++ 2020 KAKAO BLIND RECRUITMENT - 가사 검색(Level 4) (0) | 2020.05.07 |
| 프로그래머스] C++ 2018 KAKAO BLIND RECRUITMENT - [3차] n진수(Level 2) (0) | 2020.04.30 |
| 프로그래머스] C++ 2018 KAKAO BLIND RECRUITMENT - [3차] 파일명 정렬(Level 2) (0) | 2020.04.30 |
댓글