문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/42893
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문자열 파싱 문제였습니다.
알고리즘은 아래와 같습니다.
1. 인덱스, 기본 점수, 본인 링크를 외부 링크로 갖는 인덱스들을 모아놓은 벡터, 그리고 링크를 변수로 갖는 WebPage 구조체를 선언해주고 각 page와 1:1 관계의 WebPage형 벡터를 선언해줍니다.
2. 우선 pages를 순회하며 각각의 링크를 구한 뒤 해당 링크가 몇 번째 인덱스에 매핑되는지 content2idx에 표시해줍니다.
3. pages를 순회하며 각 페이지의 기본 점수와 외부 링크를 구해준 뒤 1번에서 선언한 벡터에 저장해줍니다.
3.1 contenet2idx 맵을 통해 외부 링크에 속하는 page를 찾은 뒤 해당 page의 linkToMes 벡터에 현재 페이지 인덱스를 추가해줍니다.
4. pair<double, int>형 벡터를 선언해준 뒤 모든 { page의 총합 점수, page의 인덱스 }를 넣어줍니다.
5. 문제의 조건에 맞게 4번에서 선언한 벡터를 정렬한 뒤 제일 우선순위가 높은 page의 인덱스를 반환해줍니다.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <string> | |
| #include <vector> | |
| #include <iostream> | |
| #include <algorithm> | |
| #include <map> | |
| using namespace std; | |
| const string BODY_TAG_START = "<body>"; | |
| const string BODY_TAG_END = "</body>"; | |
| const string A_TAG = "<a href=\"https://"; | |
| const string CONTENT = "<meta property=\"og:url\" content=\"https://"; | |
| typedef struct | |
| { | |
| int idx; | |
| double basicScore; | |
| double externalLinkCnt; | |
| vector<int> linkToMes; | |
| } WebPage; | |
| vector<WebPage> webPages; | |
| map<string, int> content2idx; | |
| bool cmp(pair<double, int> a, pair<double, int> b) | |
| { | |
| if (a.first == b.first) | |
| { | |
| return a.second < b.second; | |
| } | |
| return a.first > b.first; | |
| } | |
| double getTotalScore(WebPage webPage) | |
| { | |
| double totalScore = webPage.basicScore; | |
| double sum = 0.0; | |
| for (int idx : webPage.linkToMes) | |
| { | |
| sum += (webPages[idx].basicScore / webPages[idx].externalLinkCnt); | |
| } | |
| totalScore += sum; | |
| return totalScore; | |
| } | |
| string getLowerCase(string s) | |
| { | |
| string lower = ""; | |
| for (char c : s) | |
| { | |
| lower += (c >= 'A' && c <= 'Z') ? c - 'A' + 'a' : c; | |
| } | |
| return lower; | |
| } | |
| int getWordCnt(string s, string word) | |
| { | |
| int startIdx = s.find(BODY_TAG_START); | |
| startIdx += BODY_TAG_START.length(); | |
| int endIdx = s.find(BODY_TAG_END); | |
| s = s.substr(startIdx, endIdx - startIdx); | |
| int cnt = 0; | |
| string temp = ""; | |
| for (char c : s) | |
| { | |
| if (!isalpha(c)) | |
| { | |
| cnt += (temp == word); | |
| temp = ""; | |
| continue; | |
| } | |
| temp += c; | |
| } | |
| return cnt; | |
| } | |
| string getContent(string s) | |
| { | |
| int idx = s.find(CONTENT); | |
| idx += CONTENT.length(); | |
| string result = ""; | |
| for (; s[idx] != '\"'; idx++) | |
| { | |
| result += s[idx]; | |
| } | |
| return result; | |
| } | |
| vector<string> getExternalLinks(string s) | |
| { | |
| vector<string> externalLinks; | |
| int idx = s.find(A_TAG); | |
| while (idx != -1) | |
| { | |
| idx += A_TAG.length(); | |
| string temp = ""; | |
| for (; s[idx] != '\"'; idx++) | |
| { | |
| temp += s[idx]; | |
| } | |
| externalLinks.push_back(temp); | |
| s = s.substr(idx); | |
| idx = s.find(A_TAG); | |
| } | |
| return externalLinks; | |
| } | |
| int solution(string word, vector<string> pages) { | |
| int idx = 0; | |
| for (string page : pages) | |
| { | |
| string content = getContent(page); | |
| vector<int> linkToMes; | |
| webPages.push_back({idx++, 0.0, 0.0, linkToMes}); | |
| content2idx[content] = idx; | |
| } | |
| for (int i = 0; i < pages.size(); i++) | |
| { | |
| pages[i] = getLowerCase(pages[i]); | |
| webPages[i].basicScore = getWordCnt(pages[i], getLowerCase(word)); | |
| vector<string> externalLinks = getExternalLinks(pages[i]); | |
| webPages[i].externalLinkCnt = externalLinks.size(); | |
| for (string link : externalLinks) | |
| { | |
| if (content2idx[link]) | |
| { | |
| webPages[content2idx[link] - 1].linkToMes.push_back(i); | |
| } | |
| } | |
| } | |
| vector<pair<double, int>> v; | |
| for (WebPage webPage : webPages) | |
| { | |
| v.push_back({getTotalScore(webPage), webPage.idx}); | |
| } | |
| sort(v.begin(), v.end(), cmp); | |
| return v[0].second; | |
| } |
개발환경: Programmers IDE
지적, 조언, 질문 환영합니다! 질문 남겨주세요~
반응형
'알고리즘 > programmers' 카테고리의 다른 글
| [Programmers] 성격 유형 검사하기 (0) | 2022.08.22 |
|---|---|
| [Programmers] 블록 이동하기 (0) | 2022.08.15 |
| [Programmers] 외벽 점검 (0) | 2022.08.09 |
| [Programmers] 공 이동 시뮬레이션 (0) | 2022.08.07 |
| [Programmers] 카드 짝 맞추기 (0) | 2022.08.05 |