- Problem Link : https://www.acmicpc.net/problem/1013
문제
- | 기호는 괄호안에 있는 것들 중 하나를 고르는 기호이다.
- + 는 바로 앞의 문자가 1번 이상 반복되는 기호이다.
- 이 때 (100+1+ | 01)+를 만족하는 문자열인지 아닌지를 파악해보자.
입력
- 첫째 줄, 테스트 케이스 T가 주어진다.
- 다음 줄, 테스크 케이스에 대한 문자열이 주어진다.
출력
- 전파가 문제에서 제시한 패턴이면 "YES" 그렇지 않은 경우는 "NO"를 출력한다.
풀이
해당 문제의 기호들은 실제로 정규 표현식의 기호와 동일한 기능을 하며 파이썬은 re 모듈로 정규 표현식을 제공한다. 저자는 기존에 정규 표현식을 배운적이 있어서 쉽게 코딩할 수 있었다. 아래 그림을 통해 정규 표현식 기호와 re 모듈의 함수를 확인할 수 있다.
정규 표현식이란?
문자열을 어떠한 패턴으로 파악하여 식별하기 위해 사용하며 특정 패턴을 지닌 문자열을 찾을 수 있어 주로 텍스트 데이터 사전 처리나 크롤링(스크래핑)에서 쓰인다.
- 이 문제에서는 특정 패턴을 지닌 문자열을 찾을 수 있는지 없는지만 파악하면 된다.
정규 표현식의 기호
| 기호 | 의미 | 매치 예 |
|---|---|---|
| . | 어떤 형태든 문자 한 글자(1자) | a..: abc, abb, acc 등 |
| ? | 바로 앞에 있는 문자, 하위 표현식이 0번 또는 1번 나타남 | a?b: ab, abb, aab 등 |
| * | 바로 앞에 있는 문자, 하위 표현식이 0번 이상 반복됨 | ab*: a, ab, abbb 등 |
| + | 바로 앞에 있는 문자, 하위 표현식이 1번 이상 반복됨 | ab+: ab, abb, abbbb 등 |
| {m} | 바로 앞에 있는 문자, 하위 표현식이 m회 나타남 | ab{2}: abb |
| {m, n} | 바로 앞에 있는 문자, 하위 표현식이 m번 이상, n번 이하 나타남 | ab{2, 4}: abb, abbb, abbbb |
| {m,} | 바로 앞에 있는 문자, 하위 표현식이 m회 이상 나타남 | ab{2,}: abb, abbb 등 |
| [] | 대괄호 안에 있는 문자 중 하나 | a[bcd]: ab, ac, ad |
| [^] | 대괄호 안에 있는 문자를 제외한 문 | a[^bcd]: aa, ae 등 |
| ^ | 바로 뒤에 있는 문자, 하위 표현식이 문자열 맨 앞에 나타남 | ^a: ab (매치 o), ba (x) |
| $ | 바로 앞에 있는 문자, 하위 표현식이 문자열 맨 뒤에 나타남 | a$: ab (매치 x), ba (o |
| () | 괄호 안의 정규식을 하위 표현식 그룹으로 만들어, 정규 표현식을 평가할 때는 하위 표현식이 가장 먼저 평가됨 | a(b|c): ab, ac |
| | | |로 분리된 문자, 문자열, 하위 표현식 중 하나 | a(b|c): ab, ac |
정규 표현식의 escape 문자
| 표현 | 설명 |
|---|---|
| \d | 숫자와 매치, [0-9]와 같음 |
| \D | 숫자가 아닌 것과 매치, [^0-9]와 같음 |
| \s | 공백(whitespace) 문자와 매치, [ \t\n\r\f\v]와 같음 |
| \S | 공백 문자가 아닌 것과 매치, [^ \t\n\r\f\v]와 같음 |
| \w | 문자+숫자+_ 중 1개와 매치, [가-힣a-zA-Z0-9_] |
| \W | 문자+숫자+_가 아닌 1개와 매치, [^가-힣a-zA-Z0-9_] |
| \\ | 메타 문자가 아닌 일반 문자 역슬래시 or 백슬래시()와 매치. 메타 문자 앞에 \을 붙이면 일반 문자를 의미함 |
위와 같은 기호와 이스케이프 문자를 사용해서 패턴을 만들고 특정 문자열에 패턴이 있는지 없는지를 판단할 수 있다. 파이썬의 re 모듈은 다음과 같은 함수들로 패턴을 찾을 수 있다.
| 모듈 함수 | 기본 사용법 | 설명(값 또는 기능) |
|---|---|---|
| re.match() | re.match(pattern, string) | 문자열(string)의 처음이 패턴(pattern)과 매치되는지 검색 (시작점 매치) |
| re.search() | re.search(pattern, string) | 문자열 전체(string)에 대해서 패턴(pattern)과 매치되는지 검색 (임의 지점 매치) |
| re.findall() | re.findall(pattern, string) | 문자열(string)에서 패턴(pattern)과 매치되는 모든 경우의 문자열을 찾아서 리스트로 리턴. 매치되는 문자열이 없다면 빈 리스트가 리턴됨 |
| re.split() | re.split(pattern, string) | 패턴(pattern)을 기준으로 문자열(string)을 분리하여 리스트로 리턴 |
| re.sub() | re.sub(pattern, repl, string) | 문자열(string)에서 패턴(pattern)과 매치되는 부분에 대해서 다른 문자열(repl)로 대체 |
| re.compile() | re.compile(pattern) | 패턴(pattern)을 패턴 객체로 컴파일. 찾고자 하는 패턴이 빈번한 경우에는 미리 컴파일해놓고 사용하면 속도와 편의성면에서 유리 |
따라서 파이썬의 re 모듈을 통해 다음과 같이 빠르고 쉽게 구현할 수 있다. 문제에서 주어지는 + 기호와 | 기호의 기능이 정규 표현식의 기호와 기능이 동일하므로 따로 수정하지 않고 바로 패턴으로 작성한 후에 fullmath를 사용해 전체 문자열이 패턴과 매치되는지 확인한다.
import re
pattern = r"(100+1+|01)+"
for _ in range(T):
print("YES" if re.fullmatch(pattern, input()[:-1]) else "NO")
그렇다면 만약에 정규 표현식을 쓰지않고 해당 문제를 풀기위해선 어떻게 해야할까?
아무래도 가장 쉬운 방법은 맨 앞에서부터 순차적으로 확인해나가는 방법일 것이다. 문자열은 100 또는 01로 시작해야한다. 이 때 100으로 시작하면 뒤에 0이 0번 이상 반복된 후 1이 1번 이상 반복된다.
따라서 문자열의 앞부분을 확인하면서 조건에 만족하면 점점 뒤로 가면서 검색하는 방법을 사용하여 문제를 해결할 수 있다. 패턴을 만족하는 앞 쪽 문자를 제거해주면서 진행할 것이므로 deque형을 사용하여 popleft 시켜주도록 했다. 이 때 모든 경우 popleft의 경우 q의 원소가 충분할 때만 popleft를 하도록 처리해야하고 원소가 부족하다면 NO라고 출력되도록 해야한다.
중요한 점은 100으로 시작하는 경우에서 예외처리가 필요한데 (01로 시작하는 경우는 01을 popleft 해주기만 하면 된다) 우선 100 뒤의 반복되는 0을 제거한 후에는 반드시 1이 1개 이상 있어야하고, 1개 이상 반복되는 1을 제거할 때 이 1이 100을 만드는 1이면 또 제거하면 안된다. (그 전 1까지 popleft 해주고 끝내준 후 다시 100으로 시작하는 문자열 처리로 넘어가야함) 이러한 예외처리를 모두 수작업을 해주면 다음과 같다.
import sys
input = sys.stdin.readline
T = int(input())
from collections import deque
ans = True
for _ in range(T):
ans = True
q = deque(input()[:-1])
while len(q) >= 2:
if len(q) >= 3 and q[0] == "1" and q[1] == "0" and q[2] == "0":
for _ in range(3):
q.popleft()
while q and q[0] == "0":
q.popleft()
if len(q) >= 3 and q[0] == "1" and q[1] == "0" and q[2] == "0":
ans = False
break
elif q and q[0] == "1":
while (
q
and q[0] == "1"
and len(q) <= 2
or q
and q[0] == "1"
and not (q[0] == "1" and q[1] == "0" and q[2] == "0")
):
q.popleft()
else:
ans = False
break
elif q[0] == "0" and q[1] == "1":
for _ in range(2):
q.popleft()
else:
ans = False
break
if len(q) != 0:
ans = False
print("YES" if ans else "NO")
기존의 정규 표현식과 비교했을때 코드도 엄청 길어지고 복잡해보인다. 정규 표현식 모듈, 라이브러리는 파이썬을 제외하고도 C/C++, Java와 같은 대중적인 언어에서도 표준 라이브러리로 제공하고 있기 때문에 사용하는 방법만 잘 알고 있다면 정규 표현식 모듈을 사용하는 것이 문자열에서 특정 패턴을 찾는 문제를 해결할 때는 굉장히 좋은 해결책이 될 수 있다.
코드
import sys
import re
input = sys.stdin.readline
T = int(input())
import re
pattern = r"(100+1+|01)+"
for _ in range(T):
print("YES" if re.fullmatch(pattern, input()[:-1]) else "NO")
