[실버 III] 9342번. 염색체

 문제 

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

9342번: 염색체

 사용 언어 

Python3

 풀이 과정 

요즘 코딩 테스트를 많이 보다 보니 내가 부족한 부분을 알았는데 그건 바로 정규표현식...! 파이썬으로 문자열 파싱은 이제 익숙하지만 복잡한 문자열 규칙에 해당하는지 확인하려면 if문을 쪼개고 쪼개는 것보단 정규표현식이 훨씬 간단하고 구현하기도 쉽다.

 

사실 보안을 공부하면서 Snort 룰 때 처음 정규표현식을 접했는데 그 때문에 정규표현식을 괜히 복잡한 영역이라고 생각해서 파이썬으로 문자열 문제는 많이 풀면서도 나중에 공부해야지... 하고 미뤘었다. 하지만 이제는 미룰 수 없었던 그것..!

 

이 문제는 딱 정규표현식을 처음 접하기에 좋았던 것 같다. 처음엔 정규표현식을 사용하지 않고 다음과 같이 풀어보려고 했는데... 대체 어떻게 조건문을 나눠야 하는지 감도 오지 않았다. 그래서 파이썬의 정규표현식을 찾아보니 진짜 너무나 간단한 문제였던것.. 정규표현식 만세🙆‍♀️

# A/B/C/D/E/F -> F -> C -> A/B/C/D/E/F
def validate(string):
    for i in range(len(string)):
        if i == 0:
            if string[i] not in ["A", "B", "C", "D", "E", "F"]:
                return "Good"
    ...?
    
    return "Infected!"

 

그렇게 답을 제출했더니 빠르게 맞았습니다!!

 

 제출 답안 

from sys import stdin
input = stdin.readline
import re

# A/B/C/D/E/F -> F -> C -> A/B/C/D/E/F
def validate(string):
    rule = re.compile("^[A-F]?A+F+C+[A-F]?$")
    result = rule.match(string)
    return result

if __name__ == "__main__":
    T = int(input())
    for _ in range(T):
        string = input()
        print("Good" if validate(string) == None else "Infected!")

 

 공부한 내용 

정규표현식 (Regular Expressions)

정규표현식이란 특정한 규칙을 가진 문자열의 집합을 표현하는 데 사용하는 형식 언어이다. 메타 문자를 사용해 식을 세우는데, 메타 문자란 문자가 가진 원래의 의미가 아닌 특별한 용도로 사용되는 문자를 말한다. 정규표현식에서 사용되는 메타 문자는 다음과 같다.

.  ^  $  *  +  ?  \  |  (  )  {  }  [  ]

 

 

파이썬에서 정규표현식을 사용하려면  re 라는 라이브러리를 사용하면 된다.  re.compile( ) 명령을 통해 정규표현식을 컴파일하여 변수에 저장한 후 사용할 수 있다.

 

compile의 괄호 안에 필요한 정규표현식을 넣으면 되는데, 문자는 대괄호 [ ]로 감싸준다. 이는 대괄호 안에 포함된 문자들 중 하나와 매치를 뜻한다. 이 때 [ ] 안의 두 문자에 -를 사용하면 두 문자 사이의 범위를 뜻하고 ^는 반대를 뜻한다.

[abc] # abc 중 하나와 매치
[a-c] # [abc]와 같음
[0-5] # [012345]와 같음
[a-zA-Z] # 모든 알파벳
[0-9] # 숫자

 

 

추가로 자주 사용하는 문자 클래스이다.

 \d   숫자 [0-9]
 \D   비숫자 [^0-9]
 \w   숫자 + 문자 [a-zA-Z0-9]
 \W   숫자 + 문자가 아닌 것 [^a-zA-Z0-9]
 \s   공백 [ \t\n\r\f\v]
 \S   비공백 [^ \t\n\r\f\v]
 \b   단어 경계 (`\w`와 `\W`의 경계)
 \B   비단어 경계

 

 

 .은 줄바꿈 문자인 \n을 제외한 모든 문자와 매치된다.

a.b # 'a + 모든 문자 + b'를 뜻함

a0b # a와 b 사이의 0은 모든 문자에 포함되므로 매치
abc # a와 b 사이에 문자가 없기 때문에 매치되지 않음

그런데 주의할 점은 [ ] 사이에서 .을 사용할 경우 문자 원래의 의미인 마침표가 된다!!!

a[.]b

a.b # a와 b 사이에 마침표가 있으므로 매치
a0b # a와 b 사이에 마침표가 없으므로 매치 안됨

 

 

다음은 *인데 앞에 오는 문자가 0개를 포함하여 몇 개가 오든 모두 매치된다.

lo*l

ll # 매치
lol # 매치
looool # 매치
lbl # 매치 안됨
loooooooooooobooooooool # 매치 안됨

 

 

반복 횟수를 지정하려면 중괄호 { }를 사용한다. {m, n}은 앞에 있는 문자가 m번에서 n번까지 반복될 때 매치되고 {m}의 형태로 사용하면 반드시 m번 반복인 경우만 매치된다.

 lo{3, 5}l
 
 ll # 매치 안됨
 lol # 매치 안됨
 loool # 매치
 loooool # 매치
 looooool # 매치 안됨

 

 

이외 사용할 수 있는 규칙은 다음과 같다.

 ^   뒤에 있는 문자로 시작
 $   앞에 있는 문자로 끝남
 ?   앞에 있는 문자가 0번 혹은 1번 존재
 +   앞에 있는 문자가 최소 1번 이상 존재

 

 

그리고 이러한 표현식들을 |로 구분하면 or의 의미가 적용되어 정규표현식들 중 하나만 만족해도 매치된다.

이외에도 꽤 많은 메소드들이 있는데 다 정리하긴 어려우니 잘 설명해 준 출처 블로그를 참고하자.

 

출처: https://nachwon.github.io/regular-expressions/

 

 다른 사람 코드 

맞힌 사람 코드 중 시간이 빠른 코드들을 보니 모두 정규표현식을 사용하지 않았다. 편하긴 하지만 if문으로 조건을 세세하게 나눠준 코드보다는 효율이 떨어지는 게 맞는 것 같다.

 

1.

import sys

T = int(sys.stdin.readline())
rule = ['A', 'B', 'C', 'D', 'E', 'F', '']
for _ in range(T):
    s = sys.stdin.readline().rstrip()
    i = 0
    stack = []
    for c in s:
        if stack:
            if stack[-1] == c:
                continue
        stack.append(c)
    short = ''.join(stack)
    if 'A' not in short:
        print('Good')
    else:
        start = short.index('A')
        if short[start:start+3] != 'AFC':
            print('Good')
        else:
            left = short[:start]
            right = short[start+3:]
            if left in rule and right in rule:
                print("Infected!")
            else:
                print('Good')

➡ 아니 슬라이싱을 이렇게 사용하는데 시간이 이렇게 빠를 수 있다니... 신기하당...

 

2.

T = int(input())
for t in range(T):
    S = input()

    answer = "Infected!"
    checks = ['A', 'B', 'C', 'D', 'E', 'F']
    pre = ''
    if S[0] not in checks or S[-1] not in checks:
        answer = "Good"
    else:
        checks = ['A', 'F', 'C']
        index = 0
        pre = 'A'
        for s in S[1:-1]:
            if pre != s:
                index += 1
                if checks[index] != s:
                    answer = "Good"
                    break
            pre = s

    print(answer)

➡ 조건문이 엄청 복잡해야 한다고 생각했는데 엄청... 간단하게 풀어버리셔서 눈물난다... 우왕...