[Python] BOJ(백준) 1013번 - Contact

링크

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

난이도(solved.ac 참고)

골드5

풀이

 

 

파이썬 정규표현식 문제이다. re(regular expression) 모듈을 불러와서 사용한다.

 

(100+1+ | 01)+ 을 해석해보려고 했는데, 이게 리스트로 하나하나 나열하는 게 불가능하다는 판단 하에 정규표현식에서 compile을 사용해서 풀어보기로 하였다. +와 (), | 등은 실제로 정규표현식에서 많이 쓰이는 연산자이다. 이 세 표현에 대해 잠깐 정리하자면

• +: + 앞에 붙은 요소가 최소 하나는 들어가야 한다는 뜻이다. 예를 들면, ab+c라고 해보자. 이것을 만족하는 배열은 { abc, abbc, abbbc, abbbbc, ... } 이렇게 있다.
• (): 괄호 안의 요소들을 하나로 묶는다는 뜻이다. 보통 괄호만 쓰이지는 않고, 묶은 요소들을 반복하거나 하고 싶을 때 사용한다. 예를 들면 (abc)+라고 해보자. 이것을 만족하는 배열은 { abc, abcabc, abcabcabc, abcabcabcabc, ... } 가 된다.
• |: 또는 을 의미한다. 예를 들면 (100+1|01) 라고 해보자. 이는 100+1을 만족하거나, 01과 매치되거나 또는 둘 다 매치되거나 하는 경우에 해당한다.

가장 많이 쓰이는 표현은 이렇게 세가지가 있고, 이외에도 여러가지가 있다. 이 문제를 풀 때 위와 같은 요소들은 사실 중요하지 않다. 왜냐면 문제에서 요구한 대로 컴파일을 해줘야 되는데, 그 기능을 re 모듈에서 제공하기 때문이다.

 

이제 (100+1+|01)+ 을 컴파일한 목록에 우리가 input으로 적은 값이 들어가는지를 판단해야 한다. 여기에서는 match 메소드를 사용한다. match 메소드는 문자열 처음부터 시작해서 패턴에 일치하는지 확인하는 형태이다. 일치여부를 확인하는 패턴이 두번째 대상 패턴의 제일 처음에 들어가기만 하면 되는 것이다. 반면에 fullmatch는 일치 여부를 확인하는 패턴과 대상 패턴이 정확하게 처음과 끝이 전부 일치해야 한다.

 

이해가 잘 가지 않을 수도 있는데, 아래 예시를 보면 이해가 잘 갈 것이다.

print(re.match('aa', 'aabbbbbb'))
print(re.match('aa', 'abaaaaa'))
print(re.fullmatch('aa', 'aabbbbbb'))
print(re.fullmatch('aabbbbbb', 'aabbbbbb'))

# 결과
<re.Match object; span=(0, 2), match='aa'>
None
None
<re.Match object; span=(0, 8), match='aabbbbbb'>

보다시피 match의 경우는 aa만 앞에 있다면 뒤에 뭐가 있든 매치가 되었음을 확인할 수 있으나 fullmatch의 경우는 정확히 똑같아야만 매치가 되었음을 확인할 수 있다.

그래서 이번 문제에서는 정확히 예제 입력의 값이 들어가야지만 YES를 반환하게끔 fullmatch를 사용하였다. 예를 들어 예제 입력에서

10010111
011000100110001

이 두 가지는 match를 사용했을 경우 YES를 반환하지만 fullmatch를 사용했을 경우 NO를 반환한다. (100+1+ | 01)+ 을 컴파일한 결과 리스트 내부에 10010111 또는 011000100110001이 맨 앞에 들어오기만 하면 뒤에 뭐가 있든 간에 무조건 YES를 반환하기 때문에 정확히 저 요소만이 들어가 있는지는 확인할 수가 없기 때문이다.