[프로그래머스] 매칭 점수 (2019 KAKAO BLIND) / python

1. 문제 설명

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

프로젝트는 검색어에 가장 잘 맞는 웹페이지를 보여주기 위해 아래와 같은 규칙으로 검색어에 대한 웹페이지의 매칭점수를 계산 하는 것이었다.

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

검색어 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을 리턴하면 된다.

2. 풀이 전 계획과 생각

위의 문제는 특정 검색어에 대한 각각의 웹페이지의 매칭점수를 구해주어 매칭점수가 가장 높은 index를 반환해주어야 하는 문제다.
매칭점수를 구해주기 위해서는 기본 점수와 링크 점수를 구해주어야 하는데, 링크 점수를 구해주기 위해서는 해당 웹페이지로부터 링크가 걸린 다른 웹페이지가 무엇인지 알아야 한다.

3. 풀이하면서 막혔던 점과 고민

🤔 각 Web Page 객체들 간의 관계(= 외부 링크)를 어떻게 구현해줄 수 있을까?

웹페이지 link : 해당 웹페이지로 가는 웹페이지 객체(또는 link) 리스트 HashMap을 만들어주자.

to_me_link[link] = [element1, element2, …]

4. 풀이

import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

class Solution {
    static int webCnt = 0;
    
    class WebPage {
        int wIndex;
        String link;
        int basicScore;
        int externalLinkCnt;
        
        public WebPage(String link, int basicScore, int externalLinkCnt) {
            this.wIndex = webCnt++;
            this.link = link;
            this.basicScore = basicScore;
            this.externalLinkCnt = externalLinkCnt;
        }
    }
    
    static HashMap<Integer, WebPage> idx2webPage = new HashMap<>();
    static HashMap<String, ArrayList<Integer>> to_me_link = new HashMap<>();
        
    static Pattern urlPattern, externalUrlPattern, wordPattern;
    static Matcher urlMatcher, externalUrlMatcher, wordMatcher;
    
    
    public int solution(String word, String[] pages) {
        urlPattern = Pattern.compile("<meta property=\\"og:url\\" content=\\"(\\\\S*)\\"");
        externalUrlPattern = Pattern.compile("<a href=\\"https://(\\\\S*)\\"");
        wordPattern = Pattern.compile("\\\\b(?i)"+word+"\\\\b");
        
        for (String page : pages) {
            // 자신의 url
            String url = getUrl(page);
            
            // basicScore
            int basicScore = getBasicScore(page);
            
            // externalLinkCnt
            ArrayList<String> externalLinks = getExternalLinks(page);
            int externalLinkCnt = externalLinks.size();
            
            // 웹페이지 객체 생성
            WebPage webPage = new WebPage(url, basicScore, externalLinkCnt);
            idx2webPage.put(webPage.wIndex, webPage);
            
            // 외부 링크 관계 설정
            for (String externalLink : externalLinks) {
                if(!to_me_link.containsKey(externalLink)) {
                    to_me_link.put(externalLink, new ArrayList<>()); 
                }  
                to_me_link.get(externalLink).add(webPage.wIndex);                
            }
        }
        
        // 각 webPage들을 순회하여 웹페이지의 매칭점수를 구하고, 매칭점수와 wID 최대로 갱신 (같으면, wID 최소로 갱신)
        int maxMatchingScore = 0;
        int answer = 0;
        
        for (WebPage currentWebPage : idx2webPage.values()) {
            int currentLinkScore = 0;

            **if (to_me_link.get(currentWebPage.link) != null)** {
                for (int externalLinkIdx : to_me_link.get(currentWebPage.link)) {
                    WebPage currentExternalWebPage = idx2webPage.get(externalLinkIdx);
                    currentLinkScore += (currentExternalWebPage.basicScore / currentExternalWebPage.externalLinkCnt);
                }
            }
            
            int currentMatchingScore = currentWebPage.basicScore + currentLinkScore;
            System.out.println(currentMatchingScore);
            if(currentMatchingScore > maxMatchingScore) {
                maxMatchingScore = currentMatchingScore;
                answer = currentWebPage.wIndex;
            } else if(currentMatchingScore == maxMatchingScore && currentWebPage.wIndex < answer) {
                answer = currentWebPage.wIndex;
            }
            
        }
        
        return answer;
    }
    
    public String getUrl(String page) {
        String url = "";
        urlMatcher = urlPattern.matcher(page);
        
        if(urlMatcher.find()) {
            url = urlMatcher.group().split("=")[2].replaceAll('\\"', "");
        }
        
        return url;
    }
    
    public int getBasicScore(String page) {
        int basicScore = 0;
        String body = page.split("<body>")[1].split("</body>")[0].replaceAll("[0-9]", " ");;
        wordMatcher = wordPattern.matcher(body);
        
        while (wordMatcher.find()) {
            basicScore++;
        }
        
        return basicScore;
    }
    
    public ArrayList<String> getExternalLinks(String page) {
        ArrayList<String> externalLinks = new ArrayList<>();
        externalUrlMatcher = externalUrlPattern.matcher(page);
            
        while (externalUrlMatcher.find()) {
            externalLinks.add(externalUrlMatcher.group().split("\\"")[1]);
        }
        
        return externalLinks;  
    }
    
}

문제점

MatchingScore를 디버깅해보니, 정수값만 들어오고, 소수점이 버려져있었다.

해결방안

MatchingScore을 계산하고 저장하는 부분을 다 int → double로 수정해주자.

5. 2차 풀이

import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

class Solution {
    static int webCnt = 0;
    
    class WebPage {
        int wIndex;
        String link;
        int basicScore;
        int externalLinkCnt;
        
        public WebPage(String link, int basicScore, int externalLinkCnt) {
            this.wIndex = webCnt++;
            this.link = link;
            this.basicScore = basicScore;
            this.externalLinkCnt = externalLinkCnt;
        }
    }
    
    static HashMap<Integer, WebPage> idx2webPage = new HashMap<>();
    static HashMap<String, ArrayList<Integer>> to_me_link = new HashMap<>();
        
    static Pattern urlPattern, externalUrlPattern, wordPattern;
    static Matcher urlMatcher, externalUrlMatcher, wordMatcher;
    
    
    public int solution(String word, String[] pages) {
        urlPattern = Pattern.compile("<meta property=\\"og:url\\" content=\\"(\\\\S*)\\"");
        externalUrlPattern = Pattern.compile("<a href=\\"https://(\\\\S*)\\"");
        wordPattern = Pattern.compile("\\\\b(?i)"+word+"\\\\b");
        
        for (String page : pages) {
            // 자신의 url
            String url = getUrl(page);
            
            // basicScore
            int basicScore = getBasicScore(page);
            
            // externalLinkCnt
            ArrayList<String> externalLinks = getExternalLinks(page);
            int externalLinkCnt = externalLinks.size();
            
            // 웹페이지 객체 생성
            WebPage webPage = new WebPage(url, basicScore, externalLinkCnt);
            idx2webPage.put(webPage.wIndex, webPage);
            
            // 외부 링크 관계 설정
            for (String externalLink : externalLinks) {
                if(!to_me_link.containsKey(externalLink)) {
                    to_me_link.put(externalLink, new ArrayList<>()); 
                }  
                to_me_link.get(externalLink).add(webPage.wIndex);                
            }
        }
        
        // 각 webPage들을 순회하여 웹페이지의 매칭점수를 구하고, 매칭점수와 wID 최대로 갱신 (같으면, wID 최소로 갱신)
        double maxMatchingScore = 0;
        int answer = 0;
        
        for (WebPage currentWebPage : idx2webPage.values()) {
            double currentLinkScore = 0;

            if (to_me_link.get(currentWebPage.link) != null) {
                for (int externalLinkIdx : to_me_link.get(currentWebPage.link)) {
                    WebPage currentExternalWebPage = idx2webPage.get(externalLinkIdx);
                    currentLinkScore += (currentExternalWebPage.basicScore **/ (double)** currentExternalWebPage.externalLinkCnt);
                }
            }
            
            double currentMatchingScore = currentWebPage.basicScore + currentLinkScore;

            if(currentMatchingScore > maxMatchingScore) {
                maxMatchingScore = currentMatchingScore;
                answer = currentWebPage.wIndex;
            } else if(currentMatchingScore == maxMatchingScore && currentWebPage.wIndex < answer) {
                answer = currentWebPage.wIndex;
            }
            
        }
        
        return answer;
    }
    
    public String getUrl(String page) {
        String url = "";
        urlMatcher = urlPattern.matcher(page);
        
        if(urlMatcher.find()) {
            url = urlMatcher.group().split("=")[2].replaceAll('\\"', "");
        }
        
        return url;
    }
    
    public int getBasicScore(String page) {
        int basicScore = 0;
        String body = page.split("<body>")[1].split("</body>")[0].replaceAll("[0-9]", " ");;
        wordMatcher = wordPattern.matcher(body);
        
        while (wordMatcher.find()) {
            basicScore++;
        }
        
        return basicScore;
    }
    
    public ArrayList<String> getExternalLinks(String page) {
        ArrayList<String> externalLinks = new ArrayList<>();
        externalUrlMatcher = externalUrlPattern.matcher(page);
            
        while (externalUrlMatcher.find()) {
            externalLinks.add(externalUrlMatcher.group().split('\\"')[1]);
        }
        
        return externalLinks;  
    }
    
}

6. 풀이 후 알게된 개념과 소감

Python에 익숙해져서 자료를 담는 수의 범위를 생각하지 않고 구현해줄 때가 있는데, 답이 나올 때의 최대 정수값을 예측하면서 자료형을 지정해주어야 하고, 답이 나올 때 실수값인지 정수값인지도 확인하면서 자료형을 지정해주어야 한다.
자기에게 링크를 걸지 않는 예외 경우가 있다. 객체가 null인 경우를 대비해서 코드를 구현해주는 습관을 들이자.
구현이 어려운 문제는 아니지만, 설계를 완벽히 못해서 구현을 자료구조를 중간에 변경했다. 설계하는 연습을 꾸준히 해야겠다.

'Problem Solving' 카테고리의 다른 글

[백준] 1034 : 램프 / python (0)	2022.09.26
[백준] 19236 : 청소년 상어 (삼성 SW 역량 테스트) / python (0)	2022.09.21
[백준] 1726 : 로봇 / python (0)	2022.09.01
[백준] 3190 : 뱀 (삼성 SW 역량 테스트) / python (0)	2022.08.20
[프로그래머스] 길 찾기 게임 (2019 KAKAO BLIND) / python (0)	2022.08.17