[백준] 4828 XML (파이썬), 정규 표현식

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

4828번: XML

정해진 규칙에 따라 입출력하는 문제이다.

 

import re
import sys

for s in sys.stdin.readlines():
    s = s.rstrip()
    print(sol(s))

일단 위와 같은 틀을 잡고 시작하자.

def sol(s):
    # 1. 32 ~ 127 검사. 해당 코드는 불필요하다.

ord가 32 ~ 127임을 검사하는 코드는 불필요하다.

    # 1. <> 검사.
    if 'method 1':
        temp = re.findall('<', s)  # 올바른 <, 틀린 <
        temp2 = re.findall('>', s)  # 올바른 >, 틀린 >
        temp3 = re.findall(
            '(<[0-9a-z]+>)|(</[0-9a-z]+>)|(<[0-9a-z]+/>)',
            s)  # 올바른 <tag>
        if not (len(temp) == len(temp2) == len(temp3)):
            return 'invalid'

1. <tag>에 쓰이는 <, >은 괜찮고 그렇지 않은 <, >가 존재한다면 틀리다.

모든 <, >의 개수를 파악하기 위해 temp, temp2를 만들어준다. <tag>에 쓰이는 올바른 <, >의 개수를 파악하기 위해 temp3을 만들어준다.

셋 모두 같다면 괜찮고 아니라면 invalid이다.

존재 여부를 괄호의 개수로 치환하는 발상을 하기 어려웠다.

    elif 'method 2':
        temp = re.findall(
            '(<[0-9a-z]+>)|(</[0-9a-z]+>)|(<[0-9a-z]+/>)|([<>])',
            s)  # 올바른 괄호, 올바른 괄호, 올바른 괄호, 틀린 괄호
        temp = [x[3] for x in temp if x[3]]
        if temp:
            return 'invalid'

or 연산자인 파이프 연산자 |는 왼쪽부터 찾아나간다. 만약 찾았다면 exhaust 시키고 다음 non-overlapping 문자열을 찾아나간다. 즉 올바른 <>짝을 먼저 찾은 뒤 틀린 <>을 찾아나간다.

findall은 non-capturing group을 해도 여전히 empty matches를 반환하기 때문에 별도로 temp 배열을 필터링해줘야 한다.

조금 더 직접적인 풀이고 떠올리기 쉽지만 디버깅을 하기 어려웠다. 초기에는 단순히 <.*>로 풀었는데 이럴 경우 올바른 <>짝을 못 찾아서 오답이 나온다.

    # 23. 문자열 검사
    # 대체가 아니라 제거해야 함. 반례 <tag>
    s = re.sub('<|>|&', '', s)

2번, 3번에 나오는 문자열은 단순히 제거해주면된다.

7lt;tag7gt;를 변환해서 <tag>로 만들고 이걸 스택에 넣는 것이 아니라, 어떤문자tag어떤문자로 취급해야 한다. 그렇다고 진짜로 제거해버리면 원래부터 없는 것과 구별이 안 되니 '어떤문자'를 넣는 게 좋다. 이 문제에서는 유니코드의 범위가 정해져있으니 한글 같은 문자를 넣으면 좋을 것이다. 현재 데이터에는 그런 반례가 없어서 그냥 지워도 정답 처리된다.

    # 1. & 검사. 4. HEX 검사.
    if 'method 1':
        temp = re.findall(
            '&x([0-9A-Fa-f][0-9A-Fa-f])+;',
            s)  # & 뒤 올바른 HEX
        temp2 = re.findall('&', s)  # &
        if len(temp) != len(temp2):
            return 'invalid'

& 뒤에 gt, lt, amp, HEX가 온다면 올바른 &이고, 아니라면 틀린 &이다. 또한 HEX도 올바라야 한다.

HEX는 짝수를 받기 때문에 ([][]) 이렇게 2자리를 만들고 괄호로 묶은 뒤 + 수량자를 붙여줬다. 이렇게 구한 & 뒤 올바른 HEX의 개수와 &의 개수를 비교해준다.

    elif 'method 2':
        temp = re.findall(
            '&(?!x([0-9A-Fa-f][0-9A-Fa-f])+;)',
            s)  # & 뒤 올바른 HEX가 오지 않는 경우
        if temp:
            return 'invalid'

조금 더 직접적인 풀이이다. & 뒤에 negative behind를 걸고 있다면 invalid이다.

    # 567. 스택 검사.
    stack = []
    temp = re.findall(
        '<([0-9a-z]+)>|<([0-9a-z]+)/>|</([0-9a-z]+)>',
        s)
    for a, b, c in temp:
        # 여는 태그, pass 태그, 닫는 태그
        if a:
            stack.append(a)
        elif b:
            pass
        elif c:
            if not stack:
                return 'invalid'
            popped = stack.pop()
            if popped != c:
                return 'invalid'
    if stack:
        return 'invalid'
    else:
        return 'valid'

567번의 스택 검사는 쉬우니 생략한다. stack.pop() 오류 처리를 위해 if not stack 조건문이 필요하다.

 

최종 코드

import re
import sys

def sol(s):
    # 1. 32 ~ 127 검사. 해당 코드는 불필요하다.
    # char32 = chr(32)
    # char127 = chr(127)
    # temp = re.search(f'[^{char32}-{char127}]', s)
    # if temp:
    #     return 'invalid'

    # 1. <> 검사.
    if 'method 1':
        temp = re.findall('<', s)  # 올바른 <, 틀린 <
        temp2 = re.findall('>', s)  # 올바른 >, 틀린 >
        temp3 = re.findall(
            '(<[0-9a-z]+>)|(</[0-9a-z]+>)|(<[0-9a-z]+/>)',
            s)  # 올바른 <tag>
        if not (len(temp) == len(temp2) == len(temp3)):
            return 'invalid'
    elif 'method 2':
        temp = re.findall(
            '(<[0-9a-z]+>)|(</[0-9a-z]+>)|(<[0-9a-z]+/>)|([<>])',
            s)  # 틀린 <, >
        temp = [x[3] for x in temp if x[3]]
        if temp:
            return 'invalid'

    # 23. 문자열 검사
    # 대체가 아니라 제거해야 함. 반례 &lt;tag&gt;
    s = re.sub('&lt;|&gt;|&amp;', '', s)

    # 1. & 검사. 4. HEX 검사.
    if 'method 1':
        temp = re.findall(
            '&x([0-9A-Fa-f][0-9A-Fa-f])+;',
            s)  # & 뒤 올바른 HEX
        temp2 = re.findall('&', s)  # &
        if len(temp) != len(temp2):
            return 'invalid'
    elif 'method 2':
        temp = re.findall(
            '&(?!x([0-9A-Fa-f][0-9A-Fa-f])+;)',
            s)  # & 뒤 올바른 HEX가 오지 않는 경우
        if temp:
            return 'invalid'

    # 567. 스택 검사.
    stack = []
    temp = re.findall(
        '<([0-9a-z]+)>|<([0-9a-z]+)/>|</([0-9a-z]+)>',
        s)
    for a, b, c in temp:
        # 여는 태그, pass 태그, 닫는 태그
        if a:
            stack.append(a)
        elif b:
            pass
        elif c:
            if not stack:
                return 'invalid'
            popped = stack.pop()
            if popped != c:
                return 'invalid'
    if stack:
        return 'invalid'
    else:
        return 'valid'

for s in sys.stdin.readlines():
    s = s.rstrip()
    print(sol(s))

 

느낀 점

1번의 <> 검사하는 데에 생각없이 <.*>를 썼다가 디버깅에 오랜 시간이 걸렸다. 문제에서 올바른 tag의 조건을 분명하게 적어줬는데 간과하는 실수를 하였다.