[백준] 17896 Meow Factor 2 (파이썬), 정규 표현식

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

17896번: Meow Factor 2

# 해석 어떤 문자열 S가 주어졌을 때, 'meow'를 포함한 S0로 변환하기 위하여 필요한 연산 시행 횟수의 최솟값을 구하여라. 연산의 종류는 다음과 같다. 1. 문자열 내의 임의의 위치에 임의의 글자를 넣는다. insert 2. 문자열 내의 임의의 위치에서 임의의 글자를 제거한다. delete 3. 문자열 내의 임의의 글자를 임의의 글자로 대체한다. replace 4. 문자열 내의 두 인접한 글자를 뒤바꾼다. swap

 

풀이 1.

최솟값을 구하는 것이니 bfs를 통해 탐색한다.

하지만 이런 풀이는 딱 봐도 문제가 있다. 연산의 가짓수는 4, 연산이 시행가능한 문자열 내의 임의의 위치는 최대 1e6, 연산이 시행가능한 글자는 최대 26(m, e, o, w, 다른 무언가 하나로 5개로 압축가능하다.)로 1e8에 달하는 매우 막대한 경우의 수다. 깊이 10은 커녕 1조차도 못 들어간다.

 

풀이 2.

하지만 잘 생각해보면 깊이 4 초과는 필요가 없다. 그 어떠한 S가 주어져도 insert 'm', insert 'e', insert 'o', insert 'w', 총 4번이면 답을 구할 수 있다. 마찬가지로 깊이 0도 큰 고민이 필요없다. S 내의 'meow'가 이미 포함되어 있다면 당연히 0이다.

if 'meow' in S:
    print(0)
elif is_1():
    print(1)
elif is_2():
    print(2)
elif is_3():
    print(3)
else:
    print(4)

이런 식의 풀이를 고려할 수 있을 것이다.

이제 is_n() 함수를 만들어야 한다. bfs와는 달리 거꾸로 생각해보자. S -> 어떤 문자열 -> 'meow'가 들어간 문자열을 만들고 어떤 문자열을 bfs로 탐색하는 것이 아니라, 'meow' -> 'meow'가 1번 변환된 문자열 -> 'meow'가 2번 변환된 문자열 -> ~~~을 생각하자.

이제 1번만 연산을 시행하면 meow를 만들어낼 수 있는 경우의 수를 생각해보자. 그리고 2번, 3번도 생각해보자. meow라는 명확한 문자열, 임의의 위치, 임의의 글자라는 것에서 정규표현식을 사용하면 편할 것이라는 힌트를 얻을 수 있다.

    p0 = ['(meow)']
    p1 = ['(eow|mow|mew|meo)',  # insert
          '(me.ow)',  # delete
          '(m.ow|me.w)',  # replace
          '(moew)']  # swap
    # p1_untrimmed = [
    #     '(eow|mow|mew|meo)',  # insert
    #     '(m.eow|me.ow|meo.w)',  # delete
    #     '(.eow|m.ow|me.w|meo.)',  # replace
    #     '(m.eow|emow|moew|mowe|meo.w)'  # swap
    # ]
    p2 = ['(me|mo|mw|eo|ew|ow)|(m.o|e.w|m..w)|(em.w|m.wo)']
    # https://blog.naver.com/jinhan814/222509018511
    p3 = ['(m|e|o|w)']

이제 경우의 수를 구했으니 중복되는 것을 쳐내가면서 머릿속으로 구현을 하면 답을 구할 수 있다.

문제는 p2를 깔끔하게 구하는 것이 어렵다는 점이다. p0은 자명하다. p4가 필요없는 것도 자명하다. p3는 조금 어렵지만 생각해낼 수 있다. p1은 (meow) 1개, 임의의 위치(좌+4개+우 = 6개),  임의의 연산(4)의 가짓수를 일일이 하면 구할 수는 있다. 하지만 p2는 어렵다. 지금도 모르겠다. 답은 해당 블로그를 참고하였다.

 

풀이 3.

하지만 우리에게는 컴퓨터가 있다. 요소 n*위치 6*연산 4 정도는 컴퓨터로 구할 수 있다.

def make_p(before):
    new = set()
    for v in before:
        for i in range(len(v)):
            new.add(v[:i]+v[i+1:])  # insert
            new.add(v[:i]+'.'+v[i+1:])  # replace
            if i >= 1:  # range(1, len(v))와 동일
                new.add(v[:i]+'.'+v[i:])  # delete
                new.add(v[:i-1] + v[i] + v[i-1] + v[i+1:])  # swap
    return new

p0 = set(['meow'])
p1 = make_p(p0)
p2 = make_p(p1)
p3 = set(['m', 'e', 'o', 'w'])
# p3 = make_p(p2)

초기값 p0를 만들어준다. 그 후 make_p 함수 속에 p0를 넣어서 p1을 만든다. 해당 행위를 반복하여 p3까지 만들어준다.

make_p 함수 자체는 다음과 같이 만들면 된다. 이전 pattern에서 요소 v를 꺼낸다. 위치 i를 결정한다. 그 후 insert, replace, delete, swap 연산을 구현해내면 된다.

참고로 현재 코드는 substring 여부를 걸러내지 못하기 때문에 비효율적이다. 풀이 2의 p1_untrimmed를 보면 'm.eow'는 언제나 '.eow'를 포함하기 때문에 불필요하다.

 

최종적인 코드는 다음과 같다.

import re

S = input()

if 'make patterns using method 1':
    p0 = ['(meow)']
    p1 = ['(eow|mow|mew|meo)',  # insert
          '(me.ow)',  # delete
          '(m.ow|me.w)',  # replace
          '(moew)']  # swap
    # p1_untrimmed = [
    #     '(eow|mow|mew|meo)',  # insert
    #     '(m.eow|me.ow|meo.w)',  # delete
    #     '(.eow|m.ow|me.w|meo.)',  # replace
    #     '(m.eow|emow|moew|mowe|meo.w)'
    # ]  # swap
    p2 = ['(me|mo|mw|eo|ew|ow)|(m.o|e.w|m..w)|(em.w|m.wo)']
    # https://blog.naver.com/jinhan814/222509018511
    p3 = ['(m|e|o|w)']
else:
    def make_p(before):
        new = set()
        for v in before:
            for i in range(len(v)):
                new.add(v[:i]+v[i+1:])  # insert
                new.add(v[:i]+'.'+v[i+1:])  # replace
                if i >= 1:  # range(1, len(v))와 동일
                    new.add(v[:i]+'.'+v[i:])  # delete
                    new.add(v[:i-1] + v[i] + v[i-1] + v[i+1:])  # swap
        return new

    p0 = set(['meow'])
    p1 = make_p(p0)
    p2 = make_p(p1)
    p3 = set(['m', 'e', 'o', 'w'])
    # p3 = make_p(p2)
    # 근본적으로 동일하지만 substring 여부를 확인하지 않아서 비효율적.
    # 'm'만 있으면 되는데 'mew..' 등도 포함되어버림.

for i, p in enumerate([p0, p1, p2, p3]):
    if re.search('|'.join(p), S):
        print(i)
        break
else:
    print(4)

 

느낀 점

문자열을 meow로 변환하는 게 아니라 거꾸로 meow를 문자열로 변환하는 발상이 어려웠다.

meow를 문자열로 변환하는 게 어려웠다.