[프로그래머스] 매칭 점수 (자바)

티스토리 뷰

문제풀이/백준 && 프로그래머스

[프로그래머스] 매칭 점수 (자바)

스헤 2020. 8. 29. 00:02

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

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

매칭 점수 프렌즈 대학교 조교였던 제이지는 허드렛일만 시키는 네오 학과장님의 마수에서 벗어나, 카카오에 입사하게 되었다. 평소에 관심있어하던 검색에 마침 결원이 발생하여, 검색개발팀�

programmers.co.kr

약 6%의 정답률인 문제입니다.

문제는 빨리 풀었으나 테스트 케이스 9번, 10번에서 막혀 엄청난 시간을 들였지만,

이 코드 저 코드 다 갖다 써서 해결했습니다.

문제 풀이 후 9번, 10번 테스트 케이스 분석하겠습니다. 많은 사람들이 애먹는 것 같네요.

이런 문제를 6%나 풀었고 프로그래머스는 레벨 3으로 매겨놨네요 ㅡㅡ

이 문제는 문자열 처리를 해서 문제의 요구사항대로만 하면 어려울 것이 없습니다.

하지만 문자열 처리가 역대급입니다.

각 웹 페이지는 기본점수, 외부 링크 수, 링크점수, 매칭점수를 가집니다.

기본점수 = 본문에서 주어진 word와 매칭되는 개수
외부 링크 수 = 본문에서 주어진 외부 링크의 개수
링크 점수 = 해당 페이지로 링크를 건 (다른 웹 페이지의 기본점수 / 외부 링크수)의 합
매칭점수 = 기본점수 + 링크 점수

기본점수 구하기)

body 부분을 뽑아서 lowercase로 만듭니다. 후에 알파벳이 아닌 문자를 모두 공백 처리합니다.

body를 공백으로 split 한 후 word와 매칭 시켜 기본점수를 구합니다.

body부분에 있으면 외부 링크에 있더라도 세야 하나 봅니다.

ex) word = "abc", body = "abc <a href="abc.com"></a>"이라면 기본점수는 2입니다.

외부 링크 수)

body부분에서 적절히 외부 링크를 뽑아서 외부 링크 수를 구합니다.

링크 점수)

저는 각 웹 페이지가 스택을 가지게 하고 이 스택에 외부 링크의 주소를 저장했습니다.

page를 2까지 읽었을 때 아직 그 뒤의 인덱스는 구성되지 않기 때문입니다.

문자열을 모두 읽어서 웹 페이지를 모두 구성했을 때 map을 통해 적절히 처리했습니다.

매칭점수)

나중에 score와 match 점수를 더하면 됩니다.

전역 변수

LinkedList <Url> list = 웹 페이지(Url)를 연결한 연결 리스트

Map <String, Integer> map = key(주소), value(그 주소의 인덱스)

메소드

int solution

각 page마다 url을 찾아줍니다.

left는 meta의 시작, right는 meta의 끝, mid는 주소를 가리킵니다.

이 구조가 나올 때까지 반복하여 찾습니다.

주소를 찾았다면 map에 index와 함께 put 해줍니다.

그리고 list에 연결해줍니다.

다음은 body를 뽑아서 기본점수와 외부 링크를 수정합니다.

점수를 다 바꿨다면 매칭점수를 업데이트합니다.

웹 페이지에 있는 Stack에는 외부 링크의 주소가 있어서 map을 통해 인덱스를 받아옵니다.

그래서 현재 페이지의 기본점수와 외부 링크 수로 해당 인덱스의 매칭 점수에 더해줍니다.

점수 관리가 끝나면 문제가 원하는 조건대로 매칭 점수의 내림차순, 인덱스의 오름차순으로 정렬한 후 0번째 값을 반환합니다.

class Url

각 웹 페이지를 정의합니다.

외부 링크의 주소를 저장하는 스택, 현재 웹 페이지의 인덱스, 현재 주소, 기본 점수, 외부 링크 수, 매칭 점수를 가집니다.

(setScore, setOuter 호출)

void setScore

body와 word를 파라미터로 받아서 처리합니다.

위에서 설명했듯이 body를 깔끔하게 정리하고 word와 매칭 시킵니다.

void setOuter

left, right로 int solution 메소드에서처럼 a태그를 집고 주소를 뽑아냅니다.

뽑아낸 주소는 스택에 넣고 외부 링크 수를 1 증가시켜줍니다.

import java.util.*;

public class pm매칭점수 {

	public LinkedList<Url> list = new LinkedList<Url>();
	public Map<String, Integer> map = new HashMap<String, Integer>();

	public int solution(String word, String[] pages) {
		for(int i = 0; i < pages.length; i++) {
			String page = pages[i];
			int left = 0;
			int right = 0;
			int mid = 0;
            
			while(mid <= left) {
				left = page.indexOf("<meta", left+1);
				right = page.indexOf(">", left);
				mid = page.lastIndexOf("https://", right);
			}
            right = page.indexOf("\"", mid);
			String url = page.substring(mid, right);
			map.put(url, i);
			list.add(new Url(i, url));

			left = page.indexOf("<body>");
			right = page.indexOf("</body>");
			String body = page.substring(left + 6, right);
			list.get(i).setScore(body, word.toLowerCase());
			list.get(i).setOuter(body);
		}

		for(int i = 0; i < list.size(); i++) {
			Url now = list.get(i);
			now.match += now.score;
			Stack<String> st = now.st;
			while(!st.isEmpty()) {
				String temp = st.pop();
				if(map.containsKey(temp)) {
					int val = map.get(temp);
					list.get(val).match += (double)now.score/now.outer;
				}
			}
		}

		Collections.sort(list, new Comparator<Url>() {
			public int compare(Url u1, Url u2) {
				if(u1.match == u2.match)
					return u1.index - u2.index;
				return Double.compare(u2.match, u1.match);
			}
		});

		return list.get(0).index;
	}

	class Url {
		Stack<String> st = new Stack<String>();
		int index;
		String name;
		int score = 0;
		int outer = 0;
		double match = 0;

		Url(int i, String n){
			index = i;
			name = n;
		}

		void setScore(String body, String word) {
			body = body.toLowerCase();
			for(int i = 0; i < body.length(); i++) {
				char c = body.charAt(i);
				if(c < 'a' || c > 'z')
					body = body.replace(c, ' ');
			}
			String s[] = body.split(" ");
			for(String sT : s)
				if(word.equals(sT))
					score++;
		}

		void setOuter(String body) {
			int left, right;

			while(body.contains("<a href=\"")) {
				left = 0;
				right = 0;
				left = body.indexOf("<a href=\"");
				right = body.indexOf("\">",left);

				String link = body.substring(left+9, right);
				body = body.substring(right, body.length());
				outer++;
				st.push(link);
			}
		}

	}

}

테스트 케이스 9번 - 오답

solution 메소드에서 웹 페이지의 주소를 뽑아낼 때를 잘 봐야 합니다.

left = page.indexOf("og:url");
left = page.indexOf("https", left+1);
right = page.indexOf("\"/>", left+1);

처음 작성한 코드입니다. 모든 예제에 og:url이 있어서 그렇게 주어지는 줄 알고 작성했습니다.

전혀 아닙니다. 9번 테스트 케이스에서는 웹 페이지의 주소를 잘 뽑아내는지 검사합니다.

while(mid <= left) {
				left = page.indexOf("<meta", left+1);
				right = page.indexOf(">", left);
				mid = page.lastIndexOf("https://", right);
			}

정답 코드

테스트 케이스 10번 - 시간 초과

setOuter 메소드에서 외부 링크의 주소를 뽑아낼 때입니다.

void setOuter(String body) {
			//a태그의 시작과 끝 인덱스
			int left = 0, right = -1;
			//body에서 가장 마지막 a태그의 종료 인덱스(a태그 말고도 다른 태그가 들어올 수 있나요??)
			int last = body.lastIndexOf("\">");
			//right가 last가 될 때까지
			while(right != last) {
				left = body.indexOf("<a href=\"", right+1);
				right = body.indexOf("\">", left+1);
				//외부 링크를 뽑아서 스택에 넣고 outer 1증가
				String link = body.substring(left+9, right);
				outer++;
				st.push(link);
			}
		}

a태그 말고는 들어온다는 소리가 없길래 믿고 작성한 코드입니다.

시원하게 당했네요. a태그 말고도 다른 태그가 있나 봅니다.

<a></a> <b></b> 이런 식으로 들어오면 while문이 끝나질 않아서 시간 초과로 예상됩니다.

하... 아무도 믿지 말고 마음대로 판단하면 안 됩니다.

while(body.contains("<a href=\"")) {
				left = 0;
				right = 0;
				left = body.indexOf("<a href=\"");
				right = body.indexOf("\">",left);

				String link = body.substring(left+9, right);
				body = body.substring(right, body.length());
				outer++;
				st.push(link);
			}

정답 코드

진짜 엄청난 시간을 들였습니다. 문제가 복잡할수록 더 꼼꼼히 읽어보고 속지 말아야겠습니다. ㅡㅡ

기분 나쁜 문제였습니다.

9번, 10번 많이 틀리는데 보고 해결하시길 바랍니다.

참고 유튜브) 제 영상 아닙니다.

https://www.youtube.com/watch?v=F3Bfy3bKHc8

저작자표시

'문제풀이 > 백준 && 프로그래머스' 카테고리의 다른 글

[프로그래머스] 보석 쇼핑 (자바) (0)	2020.08.31
[프로그래머스] 블록 게임 (자바) (0)	2020.08.29
[프로그래머스] 길 찾기 게임 (자바) (0)	2020.08.27
[프로그래머스] 문자열 압축 (자바) (2)	2020.08.27
[프로그래머스] 무지의 먹방 라이브 (자바) (0)	2020.08.27

공지사항

이 블로그는?

최근에 올라온 글

최근에 달린 댓글

Total

Today

Yesterday

TAG more

« 2024/05 »
일	월	화	수	목	금	토
			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

글 보관함

스톤헤드 부수기

티스토리 뷰