title: Programmers - 매칭 점수
date: 2022-08-17
tags:
- Algorithm
https://school.programmers.co.kr/learn/courses/30/lessons/42893
문제 요약
문제가 설명하는 것이 많다. 사진이 함께 제공된 문제 설명을 직접 보는 것이 훨씬 좋다.
문제 풀이
여러 의문을 품고 포기한 문제이다.Java와는 다르게 C++에서는 정규식 사용이 많이 번거롭다.
이 때문에 정규식을 사용하지 않고 문자열을 파싱하였으며, 이해가 안 되는 여러 동작을 만나다 결국 포기하게 되었다.<meta property="og.url"... 이라는 문구가 나올 경우, content 뒤에 나오는 것이 URL이다.<body> 부터 </body> 사이에 나오는 문자열에서 word를 찾아야 한다. 문자열과 word 전부 소문자로 바꾸고, 각 문자열의 알파벳 부분만 파싱하여 비교하였다.<a href=" 이라는 문구가 나오면 외부 링크가 있다는 것이므로 이를 파싱하여 외부 링크들을 추가해준다.
처음에는 이것들 중 일부를 묶어 pageInfo 구조체로 만들고, URL을 통해 index와 구조체를 가지는 unordered_map을 사용하였다.unordered_map 사용시 총 5개의 테스트 케이스에 실패하였고, 혹여나 하여 unordered_map 대신 vector 방식을 이용하니 단 한 개의 테스트 케이스만 실패하였다.
평소와 동일하게 사용한 unordered_map의 어느 부분에서 문제가 생기는지 파악하지 못 하였다.double을 사용하더라도 정밀도에 문제가 있나 싶어 long double로 교체해보았다.
다른 부분은 다 괜찮았으나 119번 line에서 기존의 최대 점수와 새로 링크 점수를 추가해준 페이지의 점수 비교시 double로 캐스팅하는 부분이 존재하였다.
이 부분을 long double로 교체시 한 개의 추가 테스트 케이스가 실패하는 것을 확인하였다.
너무 과한 시간을 소비하였고, 이 문제에 집중하는 것 보다 다른 문제들을 풀며 이 문제는 추후 다시 풀어보는 것이 좋다는 판단을 내렸다.
지금까지 포기한 문제들은 repository의 issue에 추가해놓았으며, 추후 해당 문제들을 다시 풀 것이다.
프로그램
#include <string>
#include <vector>
#include <cctype>
#include <algorithm>
using std :: string ;
using std :: vector ;
using std :: tolower ;
struct pageInfo
{
string strURL ;
vector < string > vExtref ;
int iBasicScore ;
long double ldLinkScore ;
} ;
int iGetBasicScore ( string strBody , string strWord )
{
int iWordStartIndex = -1 ;
int iBodySize = strBody.size () ;
int iWordSize = strWord.size () ;
int iCount = 0 ;
std :: transform ( strBody.begin () , strBody.end () , strBody.begin () , [] ( unsigned char ch ) { return std :: tolower ( ch ) ; } ) ;
std :: transform ( strWord.begin () , strWord.end () , strWord.begin () , [] ( unsigned char ch ) { return std :: tolower ( ch ) ; } ) ;
for ( int i = 0 ; i < iBodySize ; ++i )
{
if ( ( -1 == iWordStartIndex ) && ( isalpha ( strBody [ i ] ) ) )
{
iWordStartIndex = i ;
}
else if ( ( -1 != iWordStartIndex ) && ( ! isalpha ( strBody [ i ] ) ) )
{
if ( ( iWordSize == i - iWordStartIndex ) && ( 0 == strBody.substr ( iWordStartIndex , iWordSize ).compare ( strWord ) ) )
{
++ iCount ;
}
iWordStartIndex = -1 ;
}
}
return iCount ;
}
int solution ( string word , vector < string > pages )
{
int answer = 0 ;
long double ldMaxScore = -1 ;
int iPageSize = pages.size () ;
vector < pageInfo > vPageInfo ( iPageSize ) ;
for ( int i = 0 ; i < iPageSize ; ++i )
{
string strPage = pages [ i ] ;
string strPreURL = "<meta property=\"og:url\" content=\"https://" ;
string strPreBody = "<body>" ;
string strPreRef = "<a href=\"https://" ;
string strURL = "" ;
int iTemp ;
vector < string > vExtref ;
int iBasicScore = 0 ;
iTemp = strPage.find ( strPreURL ) + strPreURL.size () ; // Find URL
while ( '\"' != strPage [ iTemp ] )
strURL += strPage [ iTemp ++ ] ;
iTemp = strPage.find ( strPreBody ) + strPreBody.size () ; // Find body section and count word
iBasicScore = iGetBasicScore ( strPage.substr ( iTemp , strPage.find ( "</body>" ) - iTemp ) , word ) ;
iTemp = strPage.find ( strPreRef ) + strPreRef.size () ; // Find external reference
while ( iTemp != string :: npos ) // If npos, can't find
{
int iEndIndex = strPage.find ( "\"" , iTemp ) ;
vExtref.emplace_back ( strPage.substr ( iTemp , iEndIndex - iTemp ) ) ;
int iNextIndex = strPage.find ( strPreRef , iTemp + 1 ) + strPreRef.size () ;
if ( iNextIndex <= iTemp )
break ;
iTemp = iNextIndex ;
}
vPageInfo [ i ].strURL = strURL ;
vPageInfo [ i ].iBasicScore = iBasicScore ;
vPageInfo [ i ].vExtref = vExtref ;
vPageInfo [ i ].ldLinkScore = 0 ;
}
for ( int i = 0 ; i < iPageSize ; ++i )
{
if ( ldMaxScore < vPageInfo [ i ].iBasicScore )
{
ldMaxScore = vPageInfo [ i ].iBasicScore ;
answer = i ;
}
int iExtrefSize = vPageInfo [ i ].vExtref.size () ;
for ( int j = 0 ; j < iExtrefSize ; ++j )
{
for ( int k = 0 ; k < iPageSize ; ++k )
{
if ( 0 == vPageInfo [ i ].vExtref [ j ].compare ( vPageInfo [ k ].strURL ) )
{
vPageInfo [ k ].ldLinkScore += ( double ) vPageInfo [ i ].iBasicScore / iExtrefSize ; // If long double, one more case failed.
if ( ldMaxScore < vPageInfo [ k ].iBasicScore + vPageInfo [ k ].ldLinkScore )
{
ldMaxScore = vPageInfo [ k ].iBasicScore + vPageInfo [ k ].ldLinkScore ;
answer = k ;
}
}
}
}
}
return answer ;
}'Judge' 카테고리의 다른 글
| Programmers - 기지국 설치 (0) | 2022.08.19 |
|---|---|
| Programmers - 스타 수열 (0) | 2022.08.18 |
| Programmers - 가장 긴 팰린드롬 (0) | 2022.08.14 |
| Programmers - 110 옮기기 (0) | 2022.08.14 |
| Programmers - 추석 트래픽 (0) | 2022.08.13 |