[C++] 프로그래머스 매칭 점수 풀이

https://programmers.co.kr/learn/courses/30/lessons/42893

코딩테스트 연습 - 매칭 점수

 

문제 풀이

이 문제는 카카오답게 문자열을 다루는 스킬을 확인하는 문제인 것 같다. 이 문제에서 찾아야할 문자열은 url, 검색하고자 하는 단어, 링크가 걸린 url을 찾아야한다. 각각 다음과 같은 방식으로 찾는다.

 

1. url 검색 : url이 담긴 문자열은 다음과 같이 시작한다.

<meta property="og:url" content="https://

이 문자열로 시작하는 부분을 찾아 content="________"에 밑줄에 해당하는 부분을 저장한다.

 

2. 검색하고자 하는 단어 : 대문자로 한 번, 소문자로 한 번 찾는다.

대문자로 문자를 바꿔주는 toupper()와 소문자로 문자를 바꿔주는 tolower를 이용해 word의 첫 문자를 대문자, 소문자로 찾아 일치하는 단어가 있는지 비교한다. 비교는 모든 문자열을 대문자로 바꿔 비교한다.

 

3. 링크가 걸린 url : 링크 주소 문자열은 다음과 같이 시작한다.

<a href=\"https://

이 문자열로 시작하는 부분을 전부 찾아 자신을 가리키는 페이지의 인덱스를 저장하는 배열에 넣어주고 현재 페이지에서 가리키는 링크의 수를 증가시킨다.

 

위의 과정대로 짠 코드이다.

 

소스 코드

#include <string>
#include <iostream>
#include <vector>
#include <map>
#include <set>
using namespace std;

string url[21]; //index - url 매핑
double basic[21]; //기본점수
int linknum[21]; //각 노드의 외부링크
map<string, set<int>> links; //자기를 가리키는 링크 저장

bool isSame(string &a, string &b) { //문자열 비교 함수
    for(int i = 0; i < a.length(); i++) {
        if(!isalpha(b[i])) { // 알파벳이 아니면 false 리턴
            return false;
            break;
        }
        if(toupper(a[i]) != toupper(b[i])) { //같지 않으면 false 리턴
            return false;
            break;
        }
    }
    return true;
} 

int solution(string word, vector<string> pages) {
    int answer = 0;
    double mnum = 0;
    for(int i = 0; i < pages.size(); i++) {
        string &now = pages[i];
        //url찾기
        int start = now.find("<meta property=\"og:url\" content=\"https://"); //url이 담긴 문자열 검색
        start += 33; //url 시작 주소로 이동
        int end = now.find("\"", start); //"로 끝나는 위치 저장
        string nowurl = now.substr(start, end - start); //url 저장
        url[i] = nowurl;
        
        
        start = now.find("<html");
        string body = now.substr(start);
        int idx = 0;
        while(idx < body.size()) { //기본 점수 계산 소문자로 찾기
            int pos = body.find(tolower(word[0]), idx);
            if(pos == string::npos) break; //단어 없으면 종료
            if(pos + word.size() > body.size()) break; //범위 벗어나면 종료
            string tmp = body.substr(pos, word.size()); //길이를 벗어나면 break
            if(word.size() == tmp.size() && isSame(word, tmp)) {//길이가 같은 문자열 저장
                if(!isalpha(body[pos-1]) && !isalpha(body[pos + word.size()])) //앞 뒤로 알파벳이 없을 때 증가
                    basic[i]+=1;
            }
            idx = pos+1;
        }
        idx = 0;
        while(idx < body.size()) { //기본 점수 계산 대문자로 찾기
            int pos = body.find(toupper(word[0]), idx); //첫 글자가 같은 위치 검색
            if(pos == string::npos) break; //단어 없으면 종료
            if(pos + word.size() > body.size()) break; //길이를 벗어나면 break
            string tmp = body.substr(pos, word.size()); //길이가 같은 문자열 저장
            if(word.size() == tmp.size() && isSame(word, tmp)) { //사이즈도 같고 같은 문자일 때
                if(!isalpha(body[pos-1]) && !isalpha(body[pos + word.size()])) //앞 뒤로 알파벳이 없을 때 증가
                    basic[i]+=1;
            }
            idx = pos+1; //다음 위치부터 다시 검색
        }
        idx = 0;
        while(idx < body.size()) { //링크 주소 찾기
            int start = body.find("<a href=\"https://", idx);
            if(start == string::npos) break;
            start += 9;
            int end = body.find("\"", start);
            string link = body.substr(start, end - start); //링크 문자열
            links[link].insert(i); //자신을 가리키는 페이지 인덱스에 insert
            linknum[i]++; //현재 페이지의 링크 수 증가
            idx = end;
        }
    }

    for(int i = 0; i < pages.size(); i++) { //최고점 찾기
        double score = basic[i]; //기본 점수
        for(auto it = links[url[i]].begin(); it != links[url[i]].end(); it++) {
            score += ((basic[*it]) / linknum[*it]); //링크 점수 더하기
        }
        if(mnum < score) { //최대값 갱신
            mnum = score;
            answer = i;
        }
    }
    


    return answer;
}

index - url 매핑한 url 배열, 기본점수를 저장할 basic 배열, 각 노드의 외부 링크 수를 저장할 linknum배열, 자신을 가리키는 링크의 인덱스를 저장할 links map을 선언하였다.

 

주의할 점과 실수한 부분

이 문제는 문자열을 파싱하는 부분이 조금 까다로웠고 점수가 double형으로 계산되어야 했다. 처음 int형으로 basic을 저장하고 캐스팅하여 점수를 계산하였을 때 몇 개의 테스트케이스를 통과하지 못했었다. 그 다음 최대값을 저장한 mnum 변수도 int형으로 선언되어있었는데 이것 때문에 8번, 17번만 통과를 하지 못하고 있었다. 이 실수를 모르고 계속 다른 부분에서 오류를 찾아 시간낭비를 많이 했다. mnum도 double로 바꾸는 순간 모든 테스트 케이스도 통과할 수 있었다.

 

채점 결과