[Baekjoon] Contact (feat. 정규표현식)

문제

“무한히 넓은 저 우주에 인류만이 홀로 존재한다면, 그건 정말 슬픈 일이 아닐까요”

푸에르토리코 아레시보에 위치한 아레시보 전파망원경(Arecibo radio telescope)은 수십 년째 존재하지 않을 지도 모르는 외계 문명으로부터의 전파를 수신하기 위해 밤하늘을 바라보고 있다.

이 망원경이 수집한 전파 속에서 자연적으로 발생하기 힘든 패턴들을 찾아내어, 그것을 증거로 외계 문명의 존재 여부를 가리려는 노력은 줄곧 이어져왔지만 아직까지도 그러한 패턴은 발견되지 않았다. 한국 천문학계의 자존심 김동혁 박사는 국내 기술로 이러한 탐사를 진행하기 위하여 다음의 전파 표기를 표준으로 삼았다.

전파의 기본 단위는 { 0 , 1 } 두 가지로 구성되어있으며, x+ (  ) 는 임의의 개수(최소 1개) x의 반복으로 이루어진 전파의 집합을 나타낸다.

(xyx)+ (  ) 는 괄호 내의 xyx의 반복으로 이루어진 전파의 집합을 뜻한다. 아래는 이해를 돕기 위한 예제이다.

• 1+ = { 1, 11, 111, 1111, 11111, … }
• 10+ = { 10, 100, 1000, 10000, 100000, … }
• (01)+ = { 01, 0101, 010101, 01010101, 0101010101, … }
• (1001)+ = { 1001, 10011001, 100110011001, … }
• 10+11 = { 1011, 10011, 100011, 1000011, 10000011, … }
• (10+1)+ = { 101, 1001, 10001, 1011001, 1001101, 100011011000001, … }

반복을 의미하는 + 외에도 or 를 의미하는 | 기호가 있다. { x | y } 는 x 혹은 y 를 의미하는 것으로, { 0+ | 1+ } 는 { 0 , 1 , 00 , 11 , 000 , 111 , … } 의 집합을 의미한다. 아래는 두 기호를 복합적으로 사용한 예이다.

• (100 | 11)+ = { 100 , 11 , 10011 , 11100 , 1110011100 , 100111111100100, … }

최근 김동혁 박사는 아레시보 전파망원경에서 star Vega(직녀성) 으로부터 수신한 전파 기록의 일부를 조사하여 그 전파들의 패턴을 분석하여 아래와 같이 기록하였다.

• (100+1+ | 01)+

김동혁 박사는 다양한 전파 기록 중에서 위의 패턴을 지니는 전파를 가려내는 프로그램을 필요로 한다. 이를 수행할 수 있는 프로그램을 작성하라.

해결

문제는 길고 읽기 굉장히 싫었지만.. 다 읽고 나면 바로 이해할 수 있는 문제였어요. 하지만 규칙을 다 만들어서 풀어야 하나? 라고 생각이 드는 문제.. 하지만 결국에는 정규표현식 문제였습니다.. 이 문제는 정규표현식에 대해서 알면 바로 풀리는 문제여서 정규표현식 기호에 대해서 조금 설명하겠습니다.

정규표현식은 문자열을 처리하는 방법 중의 하나로 특정한 조건의 문자를 검색하거나 치환하는 과정을 매우 간편하게 처리 할 수 있도록 하는 수단이라고 생활코딩에 나와있어요. 한마디로 정리하면 문장에서 원하는 문자열을 더 쉽게 찾기 위해서 생긴 표현식입니다. 그럼 바로 어떤 기호가 있는지 알아보도록 할게요.

 

^M

M이 한줄의 시작일 경우 

 

M$

M이 한줄의 끝일 경우

 

\$ or \^

문자 $와 문자 ^인 경우. 특정 역할을 하는 정규표현식 기호를 문자로 찾고 싶을 때는 항상 앞에 \를 붙여요!

 

.

모든 문자

 

..... (5개)

문자 5개

 

 [OMG]

O, M, G 중 아무 문자나 발견될 경우. 즉 []안에 있는 문자 하나라도 발견되는 경우

 

[a-zA-Z]

[]안에서 - 표현은 어디에서 어디까지로 위는 a에서 z까지, A에서 Z 중 한 문자라도 발견될 경우. 즉 이는 알파벳 문자일 경우를 뜻해요.

 

a*b

a가 0회 이상 반복되는 경우

 

a+b

a가 1회 이상 반복되는 경우

 

a?b

a가 0또는 1번 반복되는 경우

 

()

우선으로 계산해야 되는 경우

 

(a|A)

a또는 A가 발견되는 경우

 

👉 더 자세히 알고싶다면 ZVON.org를 참고해보세여

 

이정도만 알면 이 문제는 쉽게 풀립니다!!

이 문제는 100+1+ 이나 01 이 두가지 패턴이 1이상으로 반복될 경우를 찾는 문제예요. 따라서, 10000111101 같은 경우는 YES가 출력이 되야곗죠?

 

그렇다면 간단히 ((100+1+)|(01))+ 라고 쓸 수 있는데 이렇게만 쓰면 틀립니다! 왜냐면 처음과 끝부분을 고려해주셔야 해요. 이렇게만 쓴다면 1001011 같은 경우 YES가 출력되어 버려요. ^기호와 $기호를 이용해서 다시 만든다면 아래와 같이 정규표현식을 쓸 수 있습니다.

 

^((100+11*)|(01))*((100+11*)|(01))*((100+11*)|(01))*$

 

이 정규표현식을 가지고 python언어로 답을 내보면 아래와 같습니다. 나중에 Swift언어로도 정규표현식을 어떤 식으로 사용하는지 알아내서 제출해보고 싶네요.

코드

import re
n = int(input())
for _ in range(n):
    data=input()
    regex=re.compile("^((100+11*)|(01))*((100+11*)|(01))*((100+11*)|(01))*$")
    data_secured=regex.match(data)
    result="YES"
    if data_secured==None:
        result="NO"
    print(result)