이번 문제는 개인적으로 2019 카카오 코딩 테스트 문제중에 제일 어려웠다... Level 4 문제보다 어렵게 느껴졌는데, 처음 접근은 맞게 했는데 도중에 문자열 처리에서 애를 먹었다. 처음 보는 메서드로 쉽게 해결이 가능한 부분이었는데 이 부분은 다른 사람의 코드를 풀어보면서 알게 된 부분.

 

문제 설명

매칭 점수

프렌즈 대학교 조교였던 제이지는 허드렛일만 시키는 네오 학과장님의 마수에서 벗어나, 카카오에 입사하게 되었다.
평소에 관심있어하던 검색에 마침 결원이 발생하여, 검색개발팀에 편입될 수 있었고, 대망의 첫 프로젝트를 맡게 되었다.
그 프로젝트는 검색어에 가장 잘 맞는 웹페이지를 보여주기 위해 아래와 같은 규칙으로 검색어에 대한 웹페이지의 매칭점수를 계산 하는 것이었다.

  • 한 웹페이지에 대해서 기본점수, 외부 링크 수, 링크점수, 그리고 매칭점수를 구할 수 있다.
  • 한 웹페이지의 기본점수는 해당 웹페이지의 텍스트 중, 검색어가 등장하는 횟수이다. (대소문자 무시)
  • 한 웹페이지의 외부 링크 수는 해당 웹페이지에서 다른 외부 페이지로 연결된 링크의 개수이다.
  • 한 웹페이지의 링크점수는 해당 웹페이지로 링크가 걸린 다른 웹페이지의 기본점수 ÷ 외부 링크 수의 총합이다.
  • 한 웹페이지의 매칭점수는 기본점수와 링크점수의 합으로 계산한다.

예를 들어, 다음과 같이 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> 태그의 값으로 주어진다.
  • 한 웹페이지에서 모든 외부 링크는 <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을 리턴하면 된다.

 

 

나의 풀이

 주어진 배열에서 각 문자열이 html 페이지이기 때문에, 각 문자열로 page라는 객체를 만들자 생각하고 접근하였다.

 문제는 페이지 객체가 가져야 할 속성으로 자체점수, 링크 수는 처음부터 고정적인데 링크점수와 링크점수를 포함한 매칭 점수는 다른 페이지 객체에게 영향을 받는 다는 점이었다. 내가 헤맸던 부분이 바로 한 페이지가 링크된 다른 페이지에 전달하는 링크 점수는 연쇄적이지 않기 때문에 링크되지 않은 다른페이지에는 전혀 영향을 주진 않는다. 라는 부분을 빠르게 캐치하지 못한 부분이다.

 결과적으론

 1. 모든 페이지 객체를 생성한 후,

 2. 각 페이지 객체를 가지고 기본점수/링크수 로 다른 페이지에 점수를 더해주기만 하면 되었다.

 여기까지가 구조적인 접근이었고, 다음은 문자열 처리가 문제였다.

 

 url 자체를 구하는 건 String 객체의 indexOf() 메서드로 쉽게 생각했는데 기본 점수를 어떻게 계산해야 할지가 문제였다. 주어진 단어의 앞뒤가 공백이나 특문 등이 와야 했는데 처음에는 주어진 단어가 찾아지면 바로 앞, 뒤 문자(char)를 int형으로 변형해 아스킷 값으로 a~Z사이의 범위에 들어오는지 확인해야 겠다 생각하고 코드를 구현하려다가 너무 지저분한 코드가 되는데? 싶었다. 그리고 다른 사람 코드에서 Character 클래스에 isLetter() 라는 메서드가 그 기능을 이미 제공하고 있는 걸 발견하고 해당 메서드를 사용했다.

 

 

 

전체 코드

import java.util.*;

class Solution {
    class Page {
        int idx;
        int basic, link;
        double score;

        Page(int idx, int basic, int link, double score) {
            this.idx = idx;
            this.basic = basic;
            this.link = link;
            this.score = score;
        }
    }
    public int solution(String word, String[] pages) {
        int wordLeng = word.length();
        Map<String, Integer> map = new HashMap<String, Integer>();
        List<Page> list = new ArrayList<Page>();
        word = word.toLowerCase();
        for(int i=0; i<pages.length; i++) {
            String str = pages[i] = pages[i].toLowerCase();
            int mid = 0, pl = 0, pr = 0;
            while(mid<=pl) {
                pl = str.indexOf("<meta", pl+1);
                pr = str.indexOf(">", pl);
                mid = str.lastIndexOf("https://", pr);
            }
            pr = str.indexOf("\"", mid);
            String url = str.substring(mid,pr);
            
            pl = str.indexOf("<body>", pr);
            int basic = 0;
            for(int start = pl; ; ) {
                start = str.indexOf(word, start+1);
                if(start == -1) break;
                if(!Character.isLetter(str.charAt(start-1)) &&
                   !Character.isLetter(str.charAt(start+wordLeng))) {
                    basic++;
                    start += wordLeng;
                }
            }
            
            int link = 0;
            for(int start = pl; ; ) {
                start = str.indexOf("<a href", start+1);
                if(start == -1) break;
                link++;
            }
            
            map.put(url, i);
            list.add(new Page(i, basic, link, (double)basic));
        }
        
        for(int i=0; i<pages.length; i++) {
            String str = pages[i];
            for(int pl =0, pr = 0; ; ) {
                pl = str.indexOf("<a href", pr);
                if(pl == -1) break;
                pl = str.indexOf("https://", pl);
                pr = str.indexOf("\"", pl);
                String linkurl = str.substring(pl, pr);
                
                Integer idx = map.get(linkurl);
                if(idx!=null) {
                    Page target = list.get(idx);
                    Page now_page = list.get(i);
                    target.score += (double)now_page.basic/now_page.link;
                }
            }
        }
        
        list.sort(new Comparator<Page>(){
            public int compare(Page p1, Page p2) {
                if(p1.score == p2.score)
                    return p1.idx - p2.idx;
                else if(p1.score < p2.score)
                    return 1;
                else
                    return -1;
            }
        });
        
        return list.get(0).idx;
    }
}
저작자표시

'Algorithm > Kakao Coding Test' 카테고리의 다른 글

2020 카카오 코딩 테스트 괄호 변환 java  (0) 2020.10.28
2019 카카오 코딩 테스트 블록게임 java  (0) 2020.10.05
2019 카카오 코딩 테스트 길찾기 java  (0) 2020.09.26
2019 카카오 코딩 테스트 후보키 java  (0) 2020.09.25
2019 카카오 코딩 테스트 무지의 먹방 라이브 java  (0) 2020.09.19

+ Recent posts

티스토리툴바