[백준] 22859 HTML 파싱 풀이

1. 문제에 대하여 📦

• 문제 링크: https://www.acmicpc.net/problem/22859

(1) 조건 분석 📊

/*  
* 1. main 태그 지우기 v* 2. div 별로 구분 v* 3. div에서 title 추출해서 출력 v* 4. div 내부에 P태그 하나당 다음 과정 진행  
*       (1) P 태그 내부의 모든 태그 지우기  
*       (2) 문장 시작과 끝의 공백 지우기  
*       (3) 공백 2개짜리는 하나로 바꾼다.  
*       (4) P 태그 자체를 지우기  
* */  

2. 코드가 나오기까지 🛠️

KEY WORD: 정규 표현식

1. 정규 표현식으로 div 태그 추출 -> title만 빼서 출력
2. 정규 표현식으로 p 태그 추출 -> 위의 4가지 과정 하고 글만 출력

(1) 시간복잡도 분석 ⏳

정규표현식 패턴을 찾는 Matcher는 내부적으로 문자를 하나하나씩 확인하며 무효하면 다시 다른 부분을 찾는 백트래킹으로 내부가 구현되어 있기 때문에 for문 단순 풀이보다 훨씬 느렸다.

for문으로 푼 사람들은 900ms 때가 나왔는데 내 풀이는 정규 표현식을 쓴 내 풀이는 2000ms
따라서 정규 표현식을 쓰면 코드가 간결해지긴 하지만, SQL문 풀이에서 말고는 잘 안 쓸 듯하다.

3. 코드 🌐

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

/*  
* 1. main 태그 지우기 v* 2. div 별로 구분 v* 3. div에서 title 추출해서 출력 v* 4. div 내부에 P태그 하나당 다음 과정 진행  
*       (1) P 태그 내부의 모든 태그 지우기  
*       (2) 문장 시작과 끝의 공백 지우기  
*       (3) 공백 2개짜리는 하나로 바꾼다.  
*       (4) P 태그 자체를 지우기  
* */  
/*  
* 1. split으로 '<p>'로 구분하기  
* 2. main은 버리기 div는 "\w+" 패턴으로 타이틀 제목 추출해서 출력  
* 3. p 태그의 경우 위의 과정 그대로 하나씩 진행  
* */  
public class Main {  
    static StringBuilder answer = new StringBuilder();  
    static HashMap<Integer, String> location = new HashMap<>();  
    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        String html = br.readLine();  
        Matcher title = Pattern.compile("<div title=\"(\\w|_|\\s)*\">").matcher(html);  
        Matcher paragraph = Pattern.compile("<p>(\\w|\\s|</?[^p]>|</?\\w{2,}\\s?>|\\.)*</p>").matcher(html);  

        while(title.find()) location.put(title.start(), "title : " + title.group().replaceAll("<div title=\"(.*)\">", "$1"));  
        while (paragraph.find()){  
            String row = paragraph.group();  
            row = row.replaceAll("(</?\\w*\\s?>)", "");  
            row = row.replaceAll("\\s{2,}", " ");  
            row = row.trim();  
            location.put(paragraph.start(), row);  
        }  

        ArrayList<Integer> keys = new ArrayList<>();  
        for(int temp : location.keySet()){  
            keys.add(temp);  
        }  
        Collections.sort(keys);  

        for (int key : keys){  
            answer.append(location.get(key)).append("\n");  
        }  

        System.out.println(answer);  
    }  
}

4. 트러블 슈팅 or 배운 점📝

1. 정규 표현식은 생각보다 훨씬 느리다.
2. 정규 표현식을 부분적으로만 써서 나머지는 코드로 해결하려는 풀이는 Edge Case에서 걸리는 것 같다.

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

/*

• 1. main 태그 지우기 v
• 2. div 별로 구분 v
• 3. div에서 title 추출해서 출력 v
• 4. div 내부에 P태그 하나당 다음 과정 진행

• (1) P 태그 내부의 모든 태그 지우기

• (2) 문장 시작과 끝의 공백 지우기

• (3) 공백 2개짜리는 하나로 바꾼다.

• (4) P 태그 자체를 지우기

• /
  /

• 1. split으로 '

     '로 구분하기

• 2. main은 버리기 div는 "\w+" 패턴으로 타이틀 제목 추출해서 출력
• 3. p 태그의 경우 위의 과정 그대로 하나씩 진행

• /
  public class Main {
  static Pattern title = Pattern.compile(""."");
  static StringBuilder answer = new StringBuilder();
  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String html = br.readLine();
    String [] tags = denoteByPTag(html);
    for (String row : tags){
        if(row.contains("<div")) extractTitle(row);
        else extractP(row);
    }
  
    System.out.println(answer.toString().trim());

  }

  public static String [] denoteByPTag(String html) {

    return html.split("</?(?:main|p)>");

  }

  public static void extractTitle(String row){

    Matcher findTitle = title.matcher(row);
    if(findTitle.find()){   // 매칭 시켜줘야 함.
        String title = findTitle.group();
        title = title.substring(1, title.length()-1);
        answer.append("title : ").append(title).append("\n");
    }

  }

  public static void extractP(String row) {

    if(row.trim().isEmpty()) return;
    //   (1) P 태그 내부의 모든 태그 지우기
    String [] elements = row.split("</?\\w+\\s?>");
    //   (2) 문장 시작과 끝의 공백 지우기 - 자동
    //   (3) 공백 2개짜리는 하나로 바꾼다. - 자동
    //   (4) P 태그 자체를 지우기 - 자동
    StringBuilder rowBuilder = new StringBuilder();
    for(String element : elements){
        element = element.trim();
        if(element.isEmpty()) continue;
        rowBuilder.append(element).append(" ");
    }
    answer.append(rowBuilder.toString().trim());
    answer.append("\n");

  }
  }

이렇게 부분만 빼려고 했는데 자꾸 틀린다.
즉 정규표현식을 쓸거면 모든 케이스를 산정할 수 있어야 한다.
이 부분에서도 코딩테스트에서 모든 경우의 수를 생각하여 표현식에 녹여내지 못하면 정규 표현식 풀이가 ac를 받기에는 조금 무리일 것 같다.