[프로그래머스] 매칭 점수 - JAVA (실패 CASE 포함)

프로그래머스 문제 정복기

 

2019 KAKAO BLIND RECRUITMENT

 

난이도 : Lv 3 

---

🔗 Link

---

https://programmers.co.kr/learn/courses/30/lessons/42893

코딩테스트 연습 - 매칭 점수

 

 

📑 Summary

---

 특정 규칙으로 검색어에 대한 웹페이지의 매칭점수를 계산하여, 가장 높은 웹페이지의 index을 구하는 문제이다.(단, 여러 개라면, 가장 작은 번호를 도출하면 된다.)

 

🔑 How to solve? 

---

 필자는 이 문제를 푸는데 약 3시간의 시간이 소요되었다 -_-;; 쉽게 풀릴줄 알았던 문제는 굉장회 까다로웠다. 왜 이렇게 어려웠는지 풀이를 보며 살펴보자.

 

1. 쉬운 것부터 생각하자! 🥇

 해당 문제에 필요한 알고리즘은 간단하다. 각 페이지에 대한 스코어를 모은 뒤, 가장 큰 스코어를 가진 페이지를 반환하는 것이 요점이다. 최대 값을 구하고, 그 해당하는 페이지를 반환하는 문제는 어려운 문제가 아닐 것이다. 그렇다면, 이 문제의 핵심은 각 페이지의 스코어를 정확하게 구하는 것이 된다. 

 

 

2. 스코어 구하기 왜 어려워? 🥈

 문제를 읽어보았다면, 머릿속에 10000000%의 확률로 문자열을 다루는 속도가 이 문제를 결정하겠거니, 생각이 들 것이다. 입력 문자열은 길고, 그중에서 원하는 특정 단어나, url을 뽑아야 하기 때문이다. 나 역시 문제를 보자마자, 정규식을 떠올렸다. 정규식이 효율적이라고 판단한 이유는 다음과 같다.

 

a) url형태의 주소가 너무많다. 😨

 본 페이지url, 여러 개의 외부 페이지 url을 가지고 있기 때문에, 단순한 split 만으로는 구현을 어떻게 해야 할지 감도 안 왔고, 너무 느릴 것 같다는 생각이 강했다.

 

b) word 매칭을 하기 위한 조건이 까다롭다. 😨

문제에서 파라미터로 넘어오는 word는 양 옆에 영문(a-z,A-Z)만 아니면, 모두 한 단어로 인식하기 때문에, 그 부분을 split으로 구현하기가 어려웠고, index로 생각을 하자니, 양옆 인덱스를 체크해야 하는 것이 번거롭다는 생각이 들었다.

 

이러한 이유로 정규식이 빠르다고 판단하여, 정규식을 이용하여 진행하였다. 해당 문제에서 정규식을 통해 구해야하는 값은 크게 3가지다.

 

1. 해당 페이지 URL
2. 해당 페이지가 가지고 있는 word 매칭
3. 해당 페이지가 가지고 있는 외부 URL 

즉, 3개의 정규식이 필요하다.  각 항목에 해당하는 정규식은 아래와 같다.

 

항목	정규식
해당 페이지 URL	(<meta property="og:url" content="(\S*)//(\S*)")
word 매칭	(?<=[^a-zA-Z])("+word+")[^a-zA-Z]
외부 URL	<a href="(\S*)//(\S*)"

 

 1) 해당 페이지 URL

 해당 페이지 URL을 구할 때, 맨 처음 content="(.*)//(.*\" 이렇게만 써서 테스트 케이스에서 걸렸다. 두 가지 이유가 있었는데, 하나는 meta 태그가 없는 content 속성 혹은 다른 태그를 통해 content 속성이 있는 것으로 보인다.(TC9) 따라서 meta 태그와 함께 정규식 검증을 해야 한다. 다른 한 가지는 공백을 처리해야한다. 모든 문자로 하게 되면, 공백을 포함하기에 공백을 제외한 모든 문자로 검증을 해야 한다. (이 부분을 생각하지 못하고 있어서 까다로웠다.)

 

따라서 공백을 고려하고, 프로토콜 이후 url만 가져오기 위해서 content 속성 내부를 "(\S*)//(\S*)" 로 수정하여 구성하였다. 위 정규식을 해석하자면, "meta 태그 property가 og:url인 content 타입 중에서 (프로토콜에 상관없이) 공백 없는 url 만 가져온다." 정도가 되겠다. 

 

 

2) word 매칭

 시간을 가장 많이 잡아먹게 한 놈🤬🤬🤬. 굉장히 까다로운 조건을 가지고 있다. 대소문자를 가리지 않으나, 해당 단어로 판단하기 위해선 양옆에 문자가 영문자가 아니어야 해당 단어로 판단하는 조건을 가지고 있다. 아래와 같은 식이면 모두 다 해당 단어를 매칭 하는 방법이 될 수 있다. word 매칭이 부정확하면 TC1,2,9,12에서 실패한다.

1. ([^a-zA-Z]*)("+word+")[^a-zA-Z]
2. ([^a-zA-Z])*("+word+")[^a-zA-Z]*
3. (?<=[^a-zA-Z])("+word+")[^a-zA-Z]
4. ([^a-zA-Z]*)("+word+")[a-zA-Z]* -->??? (되면 안 되는데.. 된다... TC fail case 정리하다 발견..)

(?<=) 정규표현식은 equal(=) 뒤에 들어오는 문자가 있을 때, 그다음 문자에 대해서 검증을 하겠다는 의미이다. 즉, 해당 문제에서는 영문자가 아닌 단어 뒤에 word라는 단어가 있는지 검사하며, word 다음 문자도 영문자가 아닌 단어만 추출한다 로 표현될 수 있다.

 

 

3) 외부 URL

 이 부분은 1번과 크게 다를 바 없다. 앞서 강조했듯, 공백을 고려해야 하기 때문에 표현식 \S만 잘 써준다면 문제가 없다.

 

 

3. 문제 풀이 📐

 문자열에서 필요한 데이터는 다 잘 뽑아내었다. 이제 뽑아낸 데이터를 가지고 문제를 시키는 대로 풀기만 하면 된다.

여기서부터는 크게 어려운 부분은 없을 것이다. 매칭 점수는 본 페이지의 기본 점수와 (본 페이지로 url을 가진 타 페이지 기본 점수 / 타 페이지 외부 링크 수) 점수들로 구성된다. 필자의 경우 정리가 귀찮아 페이지를 클래스로 만든 다음 처리했다.  

 

 

 

 

 

 

💡 Code

---

import java.util.ArrayList;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;



class Solution {

  
    public int solution(String word, String[] pages) {
        int answer = 0;
        word = word.toLowerCase();
        Matcher mt=null;


        PageInfo[] pageInfos = new PageInfo[pages.length];
        List<String>[] datas = new List[pages.length];

		//각페이지에 관한 정보 정리
        for(int i = 0 ; i < pages.length ; i++){
            int score = 0 ;
            pages[i] =pages[i].toLowerCase();
            datas[i] = new ArrayList<>();
            pageInfos[i] = new PageInfo();
            
            //본 페이지 url를 구하는 코드
            mt= Pattern.compile("(<meta property=\"og:url\" content=\"https://(\\S*)\")").matcher(pages[i]);
            while(mt.find()){
                String name = mt.group(2).trim();
                pageInfos[i].name =name;
            }

			//본 페이지 basicScore를 구하는 코드
            mt = Pattern.compile("(?<=[^a-zA-Z])("+word+")[^a-zA-Z]").matcher(pages[i]);
            while(mt.find()){
                score +=1;
            }
            pageInfos[i].basicScore = score;


			////본 페이지 외부 url를 구하는 코드
            mt = Pattern.compile("<a href=\"(\\S*)//(\\S*)\"").matcher(pages[i]);
            while(mt.find()){
                String url = mt.group(2).trim();
                datas[i].add(url);
            }
            pageInfos[i].linkedOutPage = datas[i];
            pageInfos[i].outerCnt = datas[i].size();

        }



		//외부 링크를 계산하여 총점을 구하는 코드 
        for(int i = 0 ; i < pageInfos.length;i++){

            for(String url : pageInfos[i].linkedOutPage){
                for(int k = 0 ; k < pageInfos.length;k++){
                    if(i == k) continue;
                    if(url.equals(pageInfos[k].name)){
                        pageInfos[k].score += (double)pageInfos[i].basicScore /pageInfos[i].linkedOutPage.size();
                    }
                }
            }
        }

		//최대 스코어의 index를 구하는 코드 
        
        double max = 0;
		for(int i = 0 ; i < pageInfos.length;i++) {
            if(max < (pageInfos[i].basicScore+pageInfos[i].score)){
                max = (pageInfos[i].basicScore+pageInfos[i].score);
                answer = i;
            }
        }


        return answer;
    }

	
    //각 페이지가 가지고 있는 정보
    class PageInfo{
    	//본 페이지 URL
        String name;
        //본 페이지가 가지고 있는 외부 URL 갯수
        int outerCnt;
        //본 페이지가 가지고 있는 기본 Score
        int basicScore;
        //본 페이지가 가지고 있는 외부 URL 
        List<String> linkedOutPage;
        //기본 Score + 외부 url 계산 score
        double score;

    }
}

 

 

 

Fail Test Case 📌

---

50점으로 시작했다가 40점을 찍고 100점까지 올라가며, 수많은 실패 case를 마주했다. 그렇게 많이 수정했는데, 정작 수정한 부분은 저 3가지 정규식만 수정했고, 고치니까 맞았다. 그만큼 정규식만 집요하게 낸 거 같다. (-_-);;;

아래는 실패했던 것 중에서 기억나는 것들 다시 돌려보고 정리한 것들이다. 도움이 되길 바란다.

 

TC 1,2,9,12++ 실패 케이스

> word 정규식이 틀렸음을 의미

 

TC 9 실패 케이스

>word 정규식에서 word부터 시작하는 경우를 고려하지 못하는 것으로 추정

 

TC 3,6,7,8,9,10,13,15 실패 케이스

> a태그가 url을 올바르게 가지고 있지 않은 경우

 

TC 3 실패 케이스

>a태그 프로토콜에("https ://") 공백이 섞인 것으로 추정

 

TC 4,6,8,10,17 실패 케이스

> a태그가 다른 속성을 갖고 있는 것으로 추정 ( <a href="https://www.naver.com" id="hi"> 

 

TC 8 실패 케이스

> float형 사용 시 부동 소수점으로 인한 실패로 추정 (집요하고도 잔인한 자식들...)

 

 

 

Comment🩹

---

 개인적으로 정규식에 대해 어느 정도 자신감이 붙었다고 생각했는데, 고려하지 못한 케이스들이 너무 많았고, 그것들을 빠르게 잡아내지 못한 것이 해당 문제를 빠르게 풀지 못한 실패 요인으로 생각된다. 실제로 시험에서 만났다면, 최초 푸는 시간은 그렇게 오래 걸리지는 않았는데, 오류를 잡다가 발목 잡혀서 다음 문제에도 집중을 못했을 것 같다. 정확하게 정규식을 표현할 수 있도록 좀 더 연마해야겠다.😊

 

---

포스팅에 문제가 있거나, 설명이 잘못된 부분 지적 환영합니다.

더 나은 퀄리티의 콘텐츠를 제공할 수 있도록 노력하겠습니다.

읽어주셔서 감사합니다.