programmers.co.kr/learn/courses/30/lessons/1836
코딩테스트 연습 - 리틀 프렌즈 사천성
리틀 프렌즈 사천성 언제나 맛있는 음식들이 가득한 평화로운 푸드 타운. 푸드 타운에서 행복하게 사는 리틀 프렌즈들은 마을에 있는 매직 스푼을 보물처럼 보관하고 있다. 매직 스푼은 재료만
programmers.co.kr
[문제 설명]
매칭 점수
프렌즈 대학교 조교였던 제이지는 허드렛일만 시키는 네오 학과장님의 마수에서 벗어나, 카카오에 입사하게 되었다.
평소에 관심있어하던 검색에 마침 결원이 발생하여, 검색개발팀에 편입될 수 있었고, 대망의 첫 프로젝트를 맡게 되었다.
그 프로젝트는 검색어에 가장 잘 맞는 웹페이지를 보여주기 위해 아래와 같은 규칙으로 검색어에 대한 웹페이지의 매칭점수를 계산 하는 것이었다.
- 한 웹페이지에 대해서 기본점수, 외부 링크 수, 링크점수, 그리고 매칭점수를 구할 수 있다.
- 한 웹페이지의 기본점수는 해당 웹페이지의 텍스트 중, 검색어가 등장하는 횟수이다. (대소문자 무시)
- 한 웹페이지의 외부 링크 수는 해당 웹페이지에서 다른 외부 페이지로 연결된 링크의 개수이다.
- 한 웹페이지의 링크점수는 해당 웹페이지로 링크가 걸린 다른 웹페이지의 기본점수 ÷ 외부 링크 수의 총합이다.
- 한 웹페이지의 매칭점수는 기본점수와 링크점수의 합으로 계산한다.
예를 들어, 다음과 같이 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의 <head> 태그 내에 <meta> 태그의 값으로 주어진다.
- 예를들어, 아래와 같은 meta tag가 있으면 이 웹페이지의 url은 https://careers.kakao.com/index 이다.
- <meta property=og:url content=https://careers.kakao.com/index />
- 한 웹페이지에서 모든 외부 링크는 <a href=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. 해당 페이지의 이름과 기본 점수를 구한다.
2. 해당 페이지의 외부 링크 개수를 센다.
3. 해당 페이지에 링크가 걸린 페이지의 이름으로 링크 점수를 준다.
4. 모든 페이지를 반복하면서 기본점수와 링크 점수를 계산한다.
조금 상세하게 들어가보자.
1. 해당 페이지의 기본 점수를 구한다.
검색어가 "aba" 일 때, "abab ababa" 는 단어 단위로 일치하는게 없다. 이러 땐 정규표현식으로 \bkeyword\b을 사용해준다.
\b는 단어 사이 경계를 지을 수 있는 정규표현식이다. 특수문자는 경계 대상이 되지 않는다. 즉 단어랑 숫자가 양 옆에 있을 땐 단어로 보지 않는다.
하지만 문제에서는 다른 모든 문자로 단어를 구분한다했다. 즉 숫자도 특문도 단어를 구분 지을수 있다는 말이다.
그러면 <body>~</body> 부분에 있는 숫자를 공백으로 바꿔준다면 숫자가 포함된 단어도 올바른 단어로 인식할 수 있다.
해당 페이지 이름은 content="~~"부분으로 구한다. 코드를 보면 이해할 수 있다.
2. 해당 페이지의 외부 링크와 개수를 센다.
외부 링크 개수는 <a href="~~">방식으로 있다. Pattern, Matcher 클래스의 도움을 받았다. 정규표현식으로 외부 링크들을 구하고 arrayList에 넣어주었다. arrayList의 크기가 곧 개수가 된다.
3. 해당 페이지에 링크가 걸린 페이지의 이름으로 링크 점수를 준다.
1. 2번 과정을 거쳐 우리는 해당 페이지의 기본점수, 외부 링크, 외부 링크 개수를 구했다. 이제 외부 링크에 해당하는 페이지에 기본점수 / 외부 링크 개수 값을 넣어줘야 한다.
HashMap을 이용했고 HashMap의 getOrDefault 메서드를 썼다.
getOrDefault는 값이 있으면 그 값을, 없으면 Default(파라미터)에 해당하는 값을 반환한다.
4. 모든 페이지를 반복하면서 기본점수와 링크 점수를 계산한다.
모든 페이지에 대해 1, 2, 3번을 수행하면 우리에겐 기본점수(HashMap), 링크점수(HashMap)이 남는다.
더하고 최댓값이면서 가장 빠른 페이지의 인덱스를 반환하면 된다.
[코드]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
|
public int solution(String word, String[] pages) {
HashMap<String, Double> basicScore = new HashMap<String, Double>(); //기본 점수
HashMap<String, Double> linkScore = new HashMap<String, Double>(); //링크 점수
ArrayList<String> names = new ArrayList<String>(); //페이지 순서
int answer = 0; //최소 인덱스
word = word.toLowerCase(); //키워드 소문자 만들기
for(int i = 0; i < pages.length; i++) {
pages[i] = pages[i].toLowerCase(); //전부 소문자 만들기
}
for(int i = 0; i < pages.length; i++) { //링크 점수 만들기
int basic = 0; //기본점수
int outlinkCount = 0; //외부 개수
int hit = 0; //키워드 매칭
ArrayList<String> links = new ArrayList<String>();
String pName = "";
//자기 사이트 이름 구하기
Pattern pageName = Pattern.compile("<meta property=\"og:url\" content=\\S+/>");
Matcher pageNameMatcher = pageName.matcher(pages[i].split("</head>")[0]);
if(pageNameMatcher.find()) {
pName = pageNameMatcher.group(); //content="https://a.com"/>
}
pName = pName.substring(32); //"https://a.com"/>
pName = pName.substring(0,pName.length()-2); //"https://a.com"
names.add(pName);
//hashMap
String temp = pages[i];
temp = temp.split("<body>")[1].replaceAll("[0-9]", " ");
Pattern pattern = Pattern.compile("\\b"+word+"\\b");
Matcher matcher = pattern.matcher(temp);
while(matcher.find()) {
matcher.group();
hit++;
}
basic = hit; //현재 페이지 기본점수
basicScore.put(pName, (double)basic); //기본 점수 구함
// 연결된 링크 이름 구하고, 그 개수만큼 그 링크에 링크점수 던지기
temp = pages[i];
temp = temp.split("<body>")[1]; //바디 부분만 외부링크 확인
Pattern linkPattern = Pattern.compile("<a href=\\S+>");
Matcher linkMatcher = linkPattern.matcher(temp);
while(linkMatcher.find()) {
String tempGroup = linkMatcher.group(); //<a href="https://b.com">\
tempGroup = tempGroup.substring(8);
tempGroup = tempGroup.substring(0, tempGroup.length() -1);
if(tempGroup.charAt(tempGroup.length()-1) == 'a') {
tempGroup = tempGroup.substring(0, tempGroup.length()-4);
}
System.out.println(tempGroup); //"https://b.com"
links.add(tempGroup);
}
outlinkCount = links.size();
for(int j = 0; j < links.size(); j++) {
linkScore.put(links.get(j), linkScore.getOrDefault(links.get(j), 0.0) + ((double)basic / outlinkCount));
}
}
//기본 점수 + 링크 점수
Iterator<String> iter = basicScore.keySet().iterator();
HashMap<String, Double> result = new HashMap<String, Double>();
double maxV = 0;
while(iter.hasNext()) {
Double value = 0.0;
String page = iter.next();
if(linkScore.containsKey(page)) {
value = linkScore.get(page);
}
if(basicScore.containsKey(page)) {
value += basicScore.get(page);
}
result.put(page,value);
if(value > maxV) {
maxV = value;
}
}
for(int i = 0; i < names.size(); i++) { //가장 큰 값 중 가장 빠른 값 찾기
if(result.get(names.get(i)) == maxV) {
answer = i;
break;
}
}
return answer;
}
|
cs |
느낀 점: 이번 문제를 풀면서 정말 느낀 것이 많다. 그중 가장 가치 있다고 생각되는 것은, 코딩을 시작하기 전 문제의 해결 방향을 구상하지 않은 상태로 시작한다면, 결과는 시작하기 전이나 중이나 똑같다는 것이다. 물론 운이 좋으면 그럴 수 있겠지만 카카오에서는 통하지 않는 것 같다.(내 실력 기준)
codingjuny.tistory.com/39 이 분 블로그를 보면서 참 잘하신다고 생각이 들었다. 참고해도 좋을 것 같다.
'코딩테스트 > 2017 카카오 코드' 카테고리의 다른 글
| [2017 카카오코드] 카카오프렌즈 컬러링북 for JAVA (0) | 2021.06.09 |
|---|---|
| [2017 카카오코드] 4단 고음 for JAVA (0) | 2020.09.07 |
| [2017 카카오코드] 리틀 프렌즈 사천성 for JAVA (0) | 2020.09.02 |
| [2017 카카오코드] GPS for JAVA (0) | 2020.08.31 |