김낭만

재밌거나 필요하다고 생각하는 걸 만듭니다.

백준(BOJ) 22859 HTML 파싱 파이썬(Python)

문제 링크

정규표현식 문제.
파이썬은 re 모듈이 정규표현식을 지원하고, 이 모듈은 표준 라이브러리이기 때문에 조금 반칙같이 느껴지긴 하지만 문제를 케이크처럼 쉽게 먹을 수 있다.
가장 먼저, 이 문제의 효자 정규표현식인 (.*?)를 보자.
괄호는 괄호 안의 정규표현식에 매칭되는 문자열을 캡쳐(추출)하겠다는 것을 의미한다.
그리고 .은 모든 종류의 문자에 매칭될 수 있다.
*은 앞에 나온 문자(이 경우엔 ., 즉 아무 문자)가 0번 이상 반복된다는 것이다(즉, 없을 수도 있고, 1개만 있을 수도 있고, 2개 이상이 나타날 수도 있다).
?은 *앞에 붙어서 특별한 효과를 지니는데, 이는 원래 그리디(Greedy)한 방식으로 매칭하는 정규표현식을 레이지(Lazy)하게 만들어준다는 의미이다.
예를 들어보자. <p>hello world</p>에 <.*>를 매칭하면 어떻게 될까.
의도는 <p>와 </p>가 매칭되는 것이겠지만, 정규표현식은 최대한 많은 문자에 매칭하는 그리디 방식을 이용하므로 <p>hello world</p>가 한 덩어리로 매칭된다.
시작할 때의 <, 문장이 끝날 때의 > 사이에 p>hello world</p가 들어있는 것으로 보기 때문이다(즉, .*이 저 문자열에 매칭된다).
하지만, 같은 문자열에 <.*?>를 매칭하면 정규표현식은 최대한 적게, 즉 처음 만난 >까지만 .*?를 매칭하고 더 매칭하지 않는다.
즉, 결과는 원래 의도한 <p>와 </p>가 된다.
아무튼, 결과적으로 (.*?)는 가능한 적은 0개 이상의 아무 문자에 매칭하고 이를 추출해서 저장하라는 의미이다.
예를 들어, <p>(.*?)</p>는 <p></p> 태그 내부의 내용물 전부에 매칭하되, 여러 태그를 한 덩어리로 저장하지 않고 각 태그의 내용물을 저장하라는 의미가 될 것이다.
여기까지만 이해하면 쉽다. 남은 건 문제의 지시대로 정규표현식을 만들고, 문자열 내에서 모든 패턴을 찾아 리스트로 반환하는 re.findall()과 문자열 내에서 모든 패턴을 정해진 문자열로 대체하는 re.sub()를 사용하면 된다.

#!python

import re

html = input()
# 각 div별로 분리
# .*?는 0개 이상의 모든 문자에 매칭하되, Lazy하게(즉 개수를 최소로) 매칭한다는 의미
# 첫 번째 그룹은 div의 제목을 추출
# 두 번째 그룹은 div 안의 문단 내용(태그 포함)을 전부 추출
divs = re.findall('<div title="(.*?)">(.*?)</div>', html)

for title, div in divs:
    # 제목을 출력
    print('title :', title)
    # <p></p> 태그 내부의 내용물 전부 추출
    ps = re.findall('<p>(.*?)</p>', div)
    # 추출된 각 p에 대해서
    for p in ps:
        # 안쪽부터 먼저,
        # 1. 태그를 빈 문자열로 대체(삭제)
        # 2. strip() 메소드로 생긴 좌우 공백 삭제
        # 3. 최소 1개 이상의 공백을 모두 공백 하나로 대체
        # 순서가 바뀌면 제대로 처리되지 않는 예외가 생길 수 있으므로 주의
        print(re.sub(' +', ' ', re.sub('<.*?>', '', p).strip()))

2024

맨 위로 이동 ↑

2023

세그먼트 트리

개요 선형적인 자료구조에서는 값에 접근하는 데에 \(O(1)\)이면 충분하지만, 대신 부분합을 구하는 데에는 \(O(N)\)이 필요하다. 그렇다면 이 자료구조를 이진 트리로 구성하면 어떨까? 값에 접근하는 데에 걸리는 시간이 \(O(\lg N)\)으로 늘어나지만 대신 부분합을 구하...

벨만-포드 알고리즘

개요 다익스트라 알고리즘과 함께 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘보다 느리지만, 음수 가중치 간선이 있어도 작동하며, 음수 가중치 사...

다익스트라 알고리즘

개요 다익스트라 알고리즘은 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘 중 하나이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 단, 다익스트라 알고리즘은 음수 가중치 엣지를 허용하지 않는다. 이 경우에는 벨만-...

맨 위로 이동 ↑