title: Programmers - 매칭 점수
date: 2022-09-19
tags:
- Algorithm
https://school.programmers.co.kr/learn/courses/30/lessons/42893
문제 요약
문제가 설명하는 것이 많다. 사진이 함께 제공된 문제 설명을 직접 보는 것이 훨씬 좋다.
문제 풀이
이전에 실패한 문제이다.
어떠한 알고리즘에 문제가 있는건지 파악하지 못하고, 그저 정규식을 사용하지 않아서 틀렸다고 추측한 문제이다.
그동안 Devcamp로 인하여 PS를 아예 하지 못하였으며, Devcamp가 끝나 다시 PS 풀이를 재개하였다.
우선 정규식없이 풀어본 후, 정규식을 도입하려고 하였으나 갑자기 성공한 문제이다."<meta property=\"og:url\" content=\"" 가 나온다면 뒤에 해당 웹 페이지의 링크가 나오는 것이다. 웹 페이지 부분을 추출한다.
이 링크를 unordered_map을 이용하여 string을 통해 index를 알아낼 수 있도록 구성한다.<body> 부터 </body> 사이에서 단어 매칭이 이루어진다. 시작과 끝 위치를 알려준 후, 단어 매칭을 확인한다.
또한 해당 구간에서 외부 링크가 출몰하므로 "<a href=\""를 먼저 찾은 후, 이후에 나오는 외부 링크에 대해 추가해준다.
모든 정보 추출이 끝났다면 외부 링크 점수를 추가해주기 위하여 loop를 돌고, 이후 최종적으로 점수를 계산한다.
이게 끝이다. 당연히 틀릴 것이라 가정하고 제출하였으나 바로 맞춰버려서 어이가 없었다.
이전 풀이와 비교할 때, 기본 점수 부분에서 한 번 단어를 찾으면 index를 -1로 초기화한다.
이 때 문자열이 ... target target ... 방식일 경우, 뒤에 있는 target을 찾아낼 수 없다.
이 부분을 적용하여도 여전히 문제가 생기며, 프로그램이 비효율적으로 작성되어 문제를 찾기도 어렵다.
프로그램
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>
using std :: vector ;
using std :: string ;
using std :: transform ;
using std :: unordered_map ;
struct link
{
string strLink ;
vector < string > strExtLink ;
double dBasicScore ;
double dLinkScore ;
} ;
int iGetMatchingScore ( string strWord , string strPage , int iStartIndex , int iEndIndex )
{
int iIndex = iStartIndex ;
int iScore = 0 ;
transform ( strWord.begin () , strWord.end () , strWord.begin () , :: tolower ) ;
for ( int i = iStartIndex ; i < iEndIndex ; ++i )
{
if ( 0 == isalpha ( strPage [ i ] ) )
{
++ iIndex ;
string strTemp = strPage.substr ( iIndex , i - iIndex ) ;
transform ( strTemp.begin () , strTemp.end () , strTemp.begin () , :: tolower ) ;
if ( 0 == strTemp.compare ( strWord ) )
++ iScore ;
iIndex = i ;
}
}
return iScore ;
}
int solution ( string word , vector < string > pages )
{
int answer = 0 ;
double dMaxScore = 0 ;
int iIndex = 0 ;
int iPageSize = pages.size () ;
string strLinkHeader = "<meta property=\"og:url\" content=\"" ;
string strExtLinkHeader = "<a href=\"" ;
vector < link > vLinks ;
unordered_map < string , int > umLinkToIndex ;
for ( int i = 0 ; i < iPageSize ; ++i )
{
link newLink ;
int iStartIndex = pages [ i ].find ( strLinkHeader ) + strLinkHeader.size () ; // Get url
int iEndIndex = pages [ i ].find ( "\"/" , iStartIndex ) ;
newLink.strLink = pages [ i ].substr ( iStartIndex , iEndIndex - iStartIndex ) ;
umLinkToIndex [ newLink.strLink ] = i + 1 ;
iStartIndex = pages [ i ].find ( "<body>" , iEndIndex ) + 6 ; // Get basic score
iEndIndex = pages [ i ].find ( "</body>" , iStartIndex ) ;
newLink.dBasicScore = iGetMatchingScore ( word , pages [ i ] , iStartIndex , iEndIndex ) ;
newLink.dLinkScore = 0 ;
for ( int j = iStartIndex ; j < iEndIndex ; ++j ) // Get external links
{
j = pages [ i ].find ( strExtLinkHeader , j ) + strExtLinkHeader.size () ;
if ( ( j == string :: npos ) || ( j < iStartIndex ) || ( j > iEndIndex ) )
break ;
int iTempEndIndex = pages [ i ].find ( "\">" , j ) ;
newLink.strExtLink.emplace_back ( pages [ i ].substr ( j , iTempEndIndex - j ) ) ;
}
vLinks.emplace_back ( newLink ) ;
}
for ( int i = 0 ; i < iPageSize ; ++i ) // Calculate link score
{
link tempLink = vLinks [ i ] ;
int iLinkSize = tempLink.strExtLink.size () ;
double dLinkScore = tempLink.dBasicScore / iLinkSize ;
for ( int j = 0 ; j < iLinkSize ; ++j )
{
int iIndex = umLinkToIndex [ tempLink.strExtLink [ j ] ] - 1 ;
if ( -1 != iIndex )
vLinks [ iIndex ].dLinkScore += dLinkScore ;
}
}
for ( int i = 0 ; i < iPageSize ; ++i )
{
link tempLink = vLinks [ i ] ;
if ( dMaxScore < tempLink.dBasicScore + tempLink.dLinkScore )
{
dMaxScore = tempLink.dBasicScore + tempLink.dLinkScore ;
answer = i ;
}
}
return answer ;
}'Judge' 카테고리의 다른 글
| Programmers - GPS (0) | 2022.09.25 |
|---|---|
| Programmers - 캠핑 (0) | 2022.09.22 |
| Programmers - 징검다리 건너기 (0) | 2022.09.06 |
| Programmers - 브라이언의 고민 (0) | 2022.08.31 |
| Programmers - 경주로 건설 (0) | 2022.08.30 |