Programmers
[프로그래머스 Level.3] 매칭 점수 (2019 KAKAO BLIND RECRUITMENT) (Java)
Devtraces
2023. 4. 21. 11:30
문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/42893
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
코딩테스트 연습 > 2019 KAKAO BLIND RECRUITMENT > 매칭 점수
문제 설명
매칭 점수
프렌즈 대학교 조교였던 제이지는 허드렛일만 시키는 네오 학과장님의 마수에서 벗어나, 카카오에 입사하게 되었다.
평소에 관심있어하던 검색에 마침 결원이 발생하여, 검색개발팀에 편입될 수 있었고, 대망의 첫 프로젝트를 맡게 되었다.
그 프로젝트는 검색어에 가장 잘 맞는 웹페이지를 보여주기 위해 아래와 같은 규칙으로 검색어에 대한 웹페이지의 매칭점수를 계산 하는 것이었다.
- 한 웹페이지에 대해서 기본점수, 외부 링크 수, 링크점수, 그리고 매칭점수를 구할 수 있다.
- 한 웹페이지의 기본점수는 해당 웹페이지의 텍스트 중, 검색어가 등장하는 횟수이다. (대소문자 무시)
- 한 웹페이지의 외부 링크 수는 해당 웹페이지에서 다른 외부 페이지로 연결된 링크의 개수이다.
- 한 웹페이지의 링크점수는 해당 웹페이지로 링크가 걸린 다른 웹페이지의 기본점수 ÷ 외부 링크 수의 총합이다.
- 한 웹페이지의 매칭점수는 기본점수와 링크점수의 합으로 계산한다.
예를 들어, 다음과 같이 A, B, C 세 개의 웹페이지가 있고, 검색어가 hi라고 하자.
이때 A 웹페이지의 매칭점수는 다음과 같이 계산할 수 있다.
- 기본 점수는 각 웹페이지에서 hi가 등장한 횟수이다.
- A,B,C 웹페이지의 기본점수는 각각 1점, 4점, 9점이다.
- 외부 링크수는 다른 웹페이지로 링크가 걸린 개수이다.
- A,B,C 웹페이지의 외부 링크 수는 각각 1점, 2점, 3점이다.
- A 웹페이지로 링크가 걸린 페이지는 B와 C가 있다.
- A 웹페이지의 링크점수는 B의 링크점수 2점(4 ÷ 2)과 C의 링크점수 3점(9 ÷ 3)을 더한 5점이 된다.
- 그러므로, A 웹페이지의 매칭점수는 기본점수 1점 + 링크점수 5점 = 6점이 된다.
검색어 word와 웹페이지의 HTML 목록인 pages가 주어졌을 때, 매칭점수가 가장 높은 웹페이지의 index를 구하라. 만약 그런 웹페이지가 여러 개라면 그중 번호가 가장 작은 것을 구하라.
제한사항
- pages는 HTML 형식의 웹페이지가 문자열 형태로 들어있는 배열이고, 길이는 1 이상 20 이하이다.
- 한 웹페이지 문자열의 길이는 1 이상 1,500 이하이다.
- 웹페이지의 index는 pages 배열의 index와 같으며 0부터 시작한다.
- 한 웹페이지의 url은 HTML의 태그 내에 태그의 값으로 주어진다.
- 예를들어, 아래와 같은 meta tag가 있으면 이 웹페이지의 url은 https://careers.kakao.com/index 이다.
- 한 웹페이지에서 모든 외부 링크는 의 형태를 가진다.
- <a> 내에 다른 attribute가 주어지는 경우는 없으며 항상 href로 연결할 사이트의 url만 포함된다.
- 위의 경우에서 해당 웹페이지는 https://careers.kakao.com/index 로 외부링크를 가지고 있다고 볼 수 있다.
- 모든 url은 https:// 로만 시작한다.
- 검색어 word는 하나의 영어 단어로만 주어지며 알파벳 소문자와 대문자로만 이루어져 있다.
- word의 길이는 1 이상 12 이하이다.
- 검색어를 찾을 때, 대소문자 구분은 무시하고 찾는다.
- 예를들어 검색어가 blind일 때, HTML 내에 Blind라는 단어가 있거나, BLIND라는 단어가 있으면 두 경우 모두 해당된다.
- 검색어는 단어 단위로 비교하며, 단어와 완전히 일치하는 경우에만 기본 점수에 반영한다.
- 단어는 알파벳을 제외한 다른 모든 문자로 구분한다.
- 예를들어 검색어가 "aba" 일 때, "abab abababa"는 단어 단위로 일치하는게 없으니, 기본 점수는 0점이 된다.
- 만약 검색어가 "aba" 라면, "aba@aba aba"는 단어 단위로 세개가 일치하므로, 기본 점수는 3점이다.
- 결과를 돌려줄때, 동일한 매칭점수를 가진 웹페이지가 여러 개라면 그중 index 번호가 가장 작은 것를 리턴한다
- 즉, 웹페이지가 세개이고, 각각 매칭점수가 3,1,3 이라면 제일 적은 index 번호인 0을 리턴하면 된다.
입출력 예 #1
- word : blind
- pages :
["<html lang=\"ko\" xml:lang=\"ko\" xmlns=\"http://www.w3.org/1999/xhtml\">\n<head>\n <meta charset=\"utf-8\">\n <meta property=\"og:url\" content=\"https://a.com\"/>\n</head> \n<body>\nBlind Lorem Blind ipsum dolor Blind test sit amet, consectetur adipiscing elit. \n<a href=\"https://b.com\"> Link to b </a>\n</body>\n</html>", "<html lang=\"ko\" xml:lang=\"ko\" xmlns=\"http://www.w3.org/1999/xhtml\">\n<head>\n <meta charset=\"utf-8\">\n <meta property=\"og:url\" content=\"https://b.com\"/>\n</head> \n<body>\nSuspendisse potenti. Vivamus venenatis tellus non turpis bibendum, \n<a href=\"https://a.com\"> Link to a </a>\nblind sed congue urna varius. Suspendisse feugiat nisl ligula, quis malesuada felis hendrerit ut.\n<a href=\"https://c.com\"> Link to c </a>\n</body>\n</html>", "<html lang=\"ko\" xml:lang=\"ko\" xmlns=\"http://www.w3.org/1999/xhtml\">\n<head>\n <meta charset=\"utf-8\">\n <meta property=\"og:url\" content=\"https://c.com\"/>\n</head> \n<body>\nUt condimentum urna at felis sodales rutrum. Sed dapibus cursus diam, non interdum nulla tempor nec. Phasellus rutrum enim at orci consectetu blind\n<a href=\"https://a.com\"> Link to a </a>\n</body>\n</html>"]
- pages는 다음과 같이 3개의 웹페이지에 해당하는 HTML 문자열이 순서대로 들어있다.
<html lang="ko" xml:lang="ko" xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta charset="utf-8">
<meta property="og:url" content="https://a.com"/>
</head>
<body>
Blind Lorem Blind ipsum dolor Blind test sit amet, consectetur adipiscing elit.
<a href="https://b.com"> Link to b </a>
</body>
</html><html lang="ko" xml:lang="ko" xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta charset="utf-8">
<meta property="og:url" content="https://b.com"/>
</head>
<body>
Suspendisse potenti. Vivamus venenatis tellus non turpis bibendum,
<a href="https://a.com"> Link to a </a>
blind sed congue urna varius. Suspendisse feugiat nisl ligula, quis malesuada felis hendrerit ut.
<a href="https://c.com"> Link to c </a>
</body>
</html><html lang="ko" xml:lang="ko" xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta charset="utf-8">
<meta property="og:url" content="https://c.com"/>
</head>
<body>
Ut condimentum urna at felis sodales rutrum. Sed dapibus cursus diam, non interdum nulla tempor nec. Phasellus rutrum enim at orci consectetu blind
<a href="https://a.com"> Link to a </a>
</body>
</html>
위의 예를 가지고 각각의 점수를 계산해보자.
- 기본점수 및 외부 링크수는 아래와 같다.
- a.com의 기본점수는 3, 외부 링크 수는 1개
- b.com의 기본점수는 1, 외부 링크 수는 2개
- c.com의 기본점수는 1, 외부 링크 수는 1개
- 링크점수는 아래와 같다.
- a.com의 링크점수는 b.com으로부터 0.5점, c.com으로부터 1점
- b.com의 링크점수는 a.com으로부터 3점
- c.com의 링크점수는 b.com으로부터 0.5점
- 각 웹 페이지의 매칭 점수는 다음과 같다.
- a.com : 4.5 점
- b.com : 4 점
- c.com : 1.5 점
따라서 매칭점수가 제일 높은 첫번째 웹 페이지의 index인 0을 리턴 하면 된다.
입출력 예 #2
- word : Muzi
- pages :
["<html lang=\"ko\" xml:lang=\"ko\" xmlns=\"http://www.w3.org/1999/xhtml\">\n<head>\n <meta charset=\"utf-8\">\n <meta property=\"og:url\" content=\"https://careers.kakao.com/interview/list\"/>\n</head> \n<body>\n<a href=\"https://programmers.co.kr/learn/courses/4673\"></a>#!MuziMuzi!)jayg07con&&\n\n</body>\n</html>", "<html lang=\"ko\" xml:lang=\"ko\" xmlns=\"http://www.w3.org/1999/xhtml\">\n<head>\n <meta charset=\"utf-8\">\n <meta property=\"og:url\" content=\"https://www.kakaocorp.com\"/>\n</head> \n<body>\ncon%\tmuzI92apeach&2<a href=\"https://hashcode.co.kr/tos\"></a>\n\n\t^\n</body>\n</html>"]
- pages는 다음과 같이 2개의 웹페이지에 해당하는 HTML 문자열이 순서대로 들어있다.
<html lang="ko" xml:lang="ko" xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta charset="utf-8">
<meta property="og:url" content="https://careers.kakao.com/interview/list"/>
</head>
<body>
<a href="https://programmers.co.kr/learn/courses/4673"></a>#!MuziMuzi!)jayg07con&&
</body>
</html><html lang="ko" xml:lang="ko" xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta charset="utf-8">
<meta property="og:url" content="https://www.kakaocorp.com"/>
</head>
<body>
con% muzI92apeach&2<a href="https://hashcode.co.kr/tos"></a>
^
</body>
</html>- 기본점수 및 외부 링크수는 아래와 같다.
- careers.kakao.com/interview/list 의 기본점수는 0, 외부 링크 수는 1개
- www.kakaocorp.com 의 기본점수는 1, 외부 링크 수는 1개
- 링크점수는 아래와 같다.
- careers.kakao.com/interview/list 의 링크점수는 0점
- www.kakaocorp.com 의 링크점수는 0점
- 각 웹 페이지의 매칭 점수는 다음과 같다.
- careers.kakao.com/interview/list : 0점
- www.kakaocorp.com : 1 점
따라서 매칭점수가 제일 높은 두번째 웹 페이지의 index인 1을 리턴 하면 된다.
나의 코드
import java.util.*;
class Solution {
public int solution(String word, String[] pages) {
int answer = 0;
Map<String, Integer> pageMap = new HashMap<>(); // key: url, value: index
ArrayList<Page> pageList = new ArrayList<>();
word = word.toLowerCase();
for(int i=0; i<pages.length; i++) {
pages[i] = pages[i].toLowerCase();
int left = 0;
int right = 0;
left = pages[i].indexOf("<meta property=\"og:url\" content="); // 메타 태그를 먼저 찾음
left = pages[i].indexOf("https://", left); // 메타 태그 찾은 다음부터 페이지 url을 찾음
right = pages[i].indexOf("\"", left); // 페이지 url 마지막 인덱스를 찾음
String url = pages[i].substring(left, right);
System.out.println("idx = " + i + " , url = " + url);
pageMap.put(url, i);
left = pages[i].indexOf("<body>", right);
int basicScore = 0;
int start = left;
while(true) {
start = pages[i].indexOf(word, start);
if(start == -1) break;
// isLetter => char 값이 문자인지 여부를 판단하여 true/false를 반환
// 단어를 포함하고 있는 단어인지 확인한 후 기본점수 증가
// 해당 단어의 앞 뒤로 문자가 아닌지 확인 (단어는 알파벳을 제외한 다른 모든 문자로 구분한다)
if(!Character.isLetter(pages[i].charAt(start-1)) && !Character.isLetter(pages[i].charAt(start + word.length()))) basicScore++;
start += word.length(); // 다음 검색을 위해 단어 길이만큼 인덱스 증가
}
System.out.println("기본점수 = " + basicScore);
int linkScore = 0;
while(true) {
left = pages[i].indexOf("<a href", left);
if(left == -1) break;
linkScore++;
left += 1; // 다음 검색을 위해 이번 링크가 검색 안되도록 인덱스 1증가
}
System.out.println("링크점수 = " + linkScore);
// 매칭 점수에는 우선 기본점수만 넣어주고 추가로 링크점수 갱신
pageList.add(new Page(i, basicScore, linkScore, (double) basicScore));
}
// 링크 점수 계산
for(int i=0; i<pages.length; i++) {
int left = 0;
int right = 0;
while(true) {
left = pages[i].indexOf("<a href", right);
if(left == -1) break;
left = pages[i].indexOf("https://", left);
right = pages[i].indexOf("\"", left);
String outLink = pages[i].substring(left, right);
Integer outLinkIdx = pageMap.get(outLink);
if(outLinkIdx != null) {
pageList.get(outLinkIdx).matching += (double) pageList.get(i).basic / (double) pageList.get(i).link;
}
left = right;
}
}
Collections.sort(pageList, new Comparator<Page>() {
@Override
public int compare(Page o1, Page o2) {
if(o1.matching == o2.matching) // 매칭 점수 같으면 index 오름차순으로
return o1.idx - o2.idx;
else if(o1.matching > o2.matching) // 매칭 점수 큰게 앞으로
return -1; // 음수면 두 원소의 위치를 교환 안함
else
return 1; // 양수면 두 원소의 위치를 교환 함
}
});
answer = pageList.get(0).idx;
return answer;
}
class Page {
int idx; // 페이지 인덱스
int basic; // 기본 점수
int link; // 외부 링크 수
double matching; // 매칭 점수
public Page(int idx, int basic, int link, double matching) {
this.idx = idx;
this.basic = basic;
this.link = link;
this.matching = matching;
}
}
}
풀이
- 기본점수와 외부 링크 수는 각각 자기 page를 살펴보면 바로 구할 수 있기 때문에 먼저 구한 후에 링크 점수를 구하여 매칭 점수를 업데이트 하는 순서로 구했다.
- 우선 key를 page url로 하고 value를 페이지 인덱스로 하는 pageMap을 생성하고 페이지 인덱스와 기본 점수, 외부 링크 수, 매칭 점수를 멤버 변수로 하는 Page 클래스를 생성하고 Page를 선언타입으로 하는 ArrayList인 pageList를 생성하였다.
- 검색어는 대소문자를 구분하지 않으므로 주어진 문자열 word를 toLowerCase()를 이용하여 소문자로 변환한다.
- 이제 pages를 순회하면서 각각의 페이지의 점수들을 구한다.
- indexOf()를 사용하며 url과 검색어를 찾기 위해 포인터로 사용할 left와 right를 0으로 초기화한다.
- 페이지의 url 앞에 붙어있는 메타 태그인 "<meta property=\"og:url\" content="를 indexOf()로 찾아 left에 저장하고 다시 left부터 시작하여 left 다음에 있는 "https://"를 indexOf()로 찾아 left에 저장한다.그러면 left에는 페이지 url의 첫 인덱스가 담겨있다. 페이지의 마지막 인덱스를 찾기 위해 url이 끝나고 "\"가 붙기 때문에 left부터 시작하여 "\"를 찾아 해당 인덱스를 right에 저장한다. (indexOf의 두 번째 파라미터는 해당 인덱스부터 시작하도록 한다. 또한, \ 와 같은 특수문자는 특수문자 뒤에 "를 붙여 검색해야 해당 특수문자를 인식한다. 따라서 indexOf("\"")로 검색해야 찾을 수 있다)
- 이제 페이지 url의 시작과 끝의 index를 찾았으니 해당 left와 right를 이용하여 substring()으로 잘라내 url을 구하고 pageMap에 해당 url을 key로 index를 value로 하여 담아준다.
- 이제 기본점수를 구하기 위해 url의 마지막 인덱스인 right부터 하여 indexOf로 "<body>"의 인덱스를 찾아 left에 저장하고 기본 점수를 카운팅 할 basicScore와 while문 내부에서 포인터로 사용할 start를 선언하고 left 값으로 초기화한다.
- 검색어의 개수를 구하기 위해 while문을 돌면서 start부터 해당 word를 찾아 인덱스를 start에 저장한다. 만약 start가 -1이라면 해당 검색어가 없는 것이므로 while문을 종료하고 아니라면 검색어가 단어에 다른 문자열에 포함되어있는 것일 수도 있기 때문에 해당 검색어가 맞는지 추가 검사를 한다. 검색어의 앞, 뒤가 문자가 아니라면 검색어로 판단한다고 주어졌으므로 isLetter()을 이용하여 검색어의 앞, 뒤 인덱스를 판단하도록 한다.
- 해당 검색어가 맞다면 start에 검색어의 길이만큼 더해주어 다음 검색어를 찾을 수 있도록 한다.
- 이렇게 기본 점수를 구했다면 linkScore를 0으로 초기화하여 외부 링크 수를 찾는다. 외부 링크 수는 "<a href"를 검색하여 찾을 수 있다. 마찬가지로 -1을 반환하면 외부 링크가 더 이상 없다는 뜻이므로 while문을 종료하고 아니라면 외부 링크 수를 증가시키고 인덱스를 1 추가하여 다음 외부 링크를 찾는다.
- 페이지의 기본 점수와 외부 링크 수를 구했으니 링크 점수를 구하면 매칭 점수도 구할 수 있기 때문에 우선 pageList에 해당 페이지의 인덱스, 기본 점수, 외부 링크 수와 매칭 점수에는 기본 점수로 Page를 생성하여 담아준다. (매칭점수는 기본 점수 + 링크 점수이기 때문에 기본 점수만 우선 넣어 놓고 링크 점수를 구한 후에 더해주면 된다)
- 링크 점수를 구하기 위해 다시 pages를 순회하면서 아까와 마찬가지로 indexOf를 이용하여 외부 링크의 url을 구한다. 외부링크의 url을 구하여 해당 url로 pageMap에서 해당 url인 페이지의 인덱스를 구하여 pageList에서 해당 페이지의 인덱스에 해당하는 Page를 가져와 해당 Page의 매칭 점수에다가 지금 페이지의 기본 점수 / 외부 링크 수를 한 값을 더해주도록 한다. 이렇게 pages를 순회하면서 해당 페이지의 외부 링크를 모두 찾아 해당 링크의 페이지 매칭 점수에 링크 점수를 모두 더해주도록 한다.
- 이제 모든 페이지의 매칭 점수를 구했으니 pageList를 매칭 점수로 내림차순 정렬, 인덱스로 오름차순 정렬하여 pageList의 0번째 인덱스의 Page의 index를 answer에 저장하고 반환하면 된다.