[백준 JAVA] 22859 HTML 파싱

22859 HTMl 파싱

https://www.acmicpc.net/problem/22859

문제설명

HTML 문자열에서 특정 태그(<div>와 <p>)의 내용을 추출하고 이를 포맷팅하여 출력한다.

<div> 태그에서는 title 속성을 추출하고

<p> 태그에서는 내용만을 추출하여 불필요한 HTML 태그를 제거해야 한다.

문제풀이

• 표준 입력에서 HTML 문자열을 읽는다.
• 정규 표현식 정의:
  • <div title="..."> 형식의 태그를 찾기 위해 정규 표현식 "<div title=\"(\\w|_|\\s)*\""를 사용한다.
  • <p> 태그와 그 내용을 찾기 위해 "<p>(\\w|\\s|</?[^p]>|</?\\w{2,}\\s?>|\\.)*</p>" 형식을 사용한다.
• 매칭 및 저장:
  • 각 정규 표현식의 Matcher를 통해 HTML 문자열에서 해당 태그를 찾아 매칭된 문자열을 저장한다.
  • <div> 태그에서 title 속성을 추출하여 맵에 저장하고, <p> 태그에서는 내용을 정리하여 저장한다.
• 정렬 및 출력:
  • 매칭된 태그의 시작 인덱스를 기준으로 정렬한다.
  • 정렬된 순서대로 각 값을 StringBuilder에 추가한 후, 최종적으로 출력다.

 

O(n log⁡ n)   시간복잡도

 

• 정규 표현식을 사용하여 문자열을 탐색하는 과정은 문자열의 길이에 비례하여 O(n) 시간 복잡도를 가진다.
• 각 태그를 찾기 위해 문자열을 여러 번 스캔하게 되므로, 최악의 경우는 두 번의 스캔을 포함하여 O(n)이다.
• 맵에 저장하고 정렬하는 과정에서 Collections.sort()를 사용하므로
• 저장된 키의 수가 m일 경우 O(m log m) 시간 복잡도가 추가된다.
• O(n + m log m)의 시간복잡도가 소요된다. 여기서 n은 문자열의 길이, m은 저장된 태그의 수이다.

 

전체코드

import java.util.*;
import java.io.*;
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();

        // title 속성을 가진 <div> 태그를 찾기 위한 정규 표현식
        Matcher m1 = Pattern.compile("<div title=\"(\\w|_|\\s)*\"").matcher(s);
        // <p> 태그와 그 내용을 찾기 위한 정규 표현식
        Matcher m2 = Pattern.compile("<p>(\\w|\\s|</?[^p]>|</?\\w{2,}\\s?>|\\.)*</p>").matcher(s);

        // 일치한 문자열과 해당 값을 저장할 맵 생성
        Map<Integer, String> map = new HashMap<>();

        // <div> 태그에서 title 속성을 찾아 맵에 저장
        while (m1.find()) {
            // 일치한 문자열에서 title 값을 추출
            String title = m1.group().split("\"")[1];
            // 시작 인덱스와 포맷된 출력을 맵에 저장
            map.put(m1.start(), "title : " + title + "\n");
        }

        // <p> 태그와 그 내용을 찾아 처리
        while (m2.find()) {
            // 일치한 문자열에서 HTML 태그 제거
            String p = m2.group().replaceAll("<[\\w\\s/]*>", "");
            // 여러 공백을 하나의 공백으로 대체
            String cleanedText = p.replaceAll("\\s{2,}", " ") + "\n";
            // 시작 인덱스와 정리된 텍스트를 맵에 저장
            map.put(m2.start(), cleanedText);
        }

        // 맵의 키(시작 인덱스)를 리스트로 생성하고 정렬
        List<Integer> list = new ArrayList<>(map.keySet());
        Collections.sort(list);

        // 정렬된 순서로 맵의 값을 StringBuilder에 추가
        for (int i : list) {
            sb.append(map.get(i));
        }

        System.out.println(sb);
    }
}