백준 1013 - Contact (Python)

 

정규표현식과 관련하여 탐욕 연산자와 나태 연산자가 있다.

탐욕 연산자는 조건에 해당하는 최대한 긴 부분을 찾는다.

나태 연산자는 조건에 해당하는 최대한 짧은 부분을 찾는다. 정량자에 ?를 붙이는 방향으로 정의된다.

 

주어진 문제는 (100+1+ | 01)+이다. 즉 100 1개 이상 뒤에 1이 1개 이상 있거나, 01이 있는 것이 반복되는 구조에 해당한다면 "YES"를, 아닌 경우에는 "NO"를 출력하는 것이다.

 

처음에는 반례가 없을 줄 알고 정규표현식을 그대로 써 문제를 푼 줄 알았다.

해당하는 것들을 다 찾은 후 그 개수가 원래의 str과 같으면 답 아니겠는가.

그런데 오답이 계속 나왔다. 찾아보니 반례는 100111001이었다.

 

100111001은 분석해보면 10011 1001로 YES가 출력되어야 맞으나, 정규표현식은 그렇게 인식하지 않는다.

+는 위에서 말했전 탐욕 연산자에 해당하니 1을 최대한 많이 뽑으니 100111과 01을 뽑아낸다.

그러면 중간에 0이 하나 비니 NO가 출력된다. 요컨대 100+1+에서 뒷부분의 1이 새로운 100+1+ 세트의 앞부분일 경우를 잡아내지 못하는 경우가 생긴다는 것이다.

 

따라서 정규 표현식은 나태 연산자, 즉 100+1+?로 수정돼야 했다.

다만 그렇게 해서 문제가 바로 풀리는 것은 아닌 게, 그러면 중간에 붕 뜨는 1 처리를 할 방법이 없지 않은가.

이 문제는 1도 따로 정규 연산식에 포함시켜 인식한 후, 그 앞의 것이 01인지를 확인해보아서 해결 가능하다.

1 앞의 01은 규칙의 오류다. 1 앞의 100+1+?는 오류가 아니다.

1 앞의 1도 그 1 앞의 100+1+?가 있으면 오류가 아니다.

그 결과 코드는 이렇게 짤 수 있다.

 

함수 선언부

 

 

100+1+?, 01, 1 중 하나로 묶어 각각의 개수를 센다.

 

그렇게 센걸 더해서 개수가 안맞으면 0이 덩그러니 있는 것이니 당연히 NO.

다만 개수가 맞다고 맞는 것은 아니다. 1이 덩그러니 있는지 아까와 같은 방법으로 확인한다.

 

Solution: