[ 백준 ] 22859 HTML 파싱 (정규표현식 풀이)

문제

 

22859번: HTML 파싱

 

---

 

코드

 

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        String s = br.readLine();

        Matcher m1 = Pattern.compile("<div title=\"(\\w|_|\\s)*\"").matcher(s);
        Matcher m2 = Pattern.compile("<p>(\\w|\\s|</?[^p]>|</?\\w{2,}\\s?>|\\.)*</p>").matcher(s);
        Map<Integer, String> map = new HashMap<>();

        while (m1.find()) map.put(m1.start(), "title : " + m1.group().split("\"")[1] + "\n");
        while (m2.find()) {
            String p = m2.group().replaceAll("<[\\w\\s/]*>", "");
            map.put(m2.start(), p.replaceAll("\\s{2,}", " ") + "\n");
        }

        List<Integer> list = new ArrayList<>(map.keySet());
        Collections.sort(list);

        for (int i : list) sb.append(map.get(i));
        System.out.println(sb);
    }
}

 

내용

 

개인적으로 정규표현식 공부를 위해 풀어보았다.

 

풀이는 매우 간단했다.

패턴을 짜서 스플릿한 문자열을 순서에 맞게 출력하면 된다.

 

Map은 '제목 - 본문 - 제목 - 본문' 순서에 맞게 출력하기위해 사용하였다.

< key : 문장들의 순서(Integer), value : 문장(String) >

key 순으로 정렬 후 출력한다.

 

패턴 공부가 익숙치 않아 살짝 해매었다.

처음에 본문 부분 패턴을 <p>.*</p> 로 설정하였다.

하지만 올바르게 매칭되지 않았고 여러 케이스를 도입해보니

패턴의 매칭은 앞에서부터 순서대로 매칭되는 것 같았다.

때문에 </p>이 .*에 포함되어 

<p>paragraph 1</p> 가 아닌

<p>paragraph 1</p><p>paragraph 2 <i>Italic Tag</i> <br > </p> 로 일치되었다.

(왜 </p>에서 잘렸는지는 아직도 모르겠다.)

 

이 문제를 피하기 위해 패턴식이 상당히 길고 복잡해졌다.

안그래도 암호같은 패턴이 더 암호처럼 되었다.

 

문제를 푸는데엔 굉장히 효율적이고, 편하다.

하지만 단계적 접근이 없어 놓치는 부분이 있을 경우 찾기 어렵고

일단 직관적이지 않다.

나도 처음 봤을 때 이게 대체 뭔가... 했었기에 좋은 코드는 아닌 것 같다.

그리고 무엇보다 걸리는 점이 있다.

바로 시간 복잡도가 미쳐버렸다.

당장 다른분들 풀이랑만 비교해봐도 압도적인 성능이다.

 

Matcher는 매칭 시 앞에서 뒤로, 후에 다시 뒤에서 앞으로 확인하는

백트래킹을 사용해 상당히 느리다고 한다.

풀이에는 정말 편하지만 ... 사용에는 고민을 해봐야할 문제인 것 같다.