[백준] #2671 잠수함식별(python)

📌문제

일반적으로 잠수함 엔진이 작동할 때에 나오는 소리는 잠수함의 종류에 따라서 다르다고 한다.

우리는 물속에서 들리는 소리의 패턴을 듣고서 그 소리가 특정한 잠수함에서 나오는 소리인지 아닌지를 알아내려고 한다. 이 문제에서는 잠수함의 소리가 두 종류의 단위 소리의 연속으로 이루어져 있고, 그 단위 소리를 각각 0과 1로 표시한다.

또, 한 특정한 소리의 반복은 ~로 표시한다. 예를 들어 x~는 x가 한번 이상 반복되는 모든 소리의 집합을 말하고, (xyz)~는 괄호 안에 있는 xyz로 표현된 소리가 한번 이상 반복되는 모든 소리의 집합을 말한다. 다음의 예를 보라.

• 1~ = {1, 11, 111, 1111, ..., 1...1, ...}
• (01)~ = {01, 0101, 010101, 01010101. ...}
• (1001)~ = {1001, 10011001, ..., 100110011001...1001, ...}
• 10~11 = {1011, 10011, 100011, ..., 1000...011, ...}
• (10~1)~ = {101, 1001, 10001, 100001, ...1011001, ...100110110001101, ...}

그리고 (x|y)는 x또는 y중에서 아무거나 하나만을 선택해서 만든 소리의 집합, 즉 집합{x, y}를 의미한다. 예를 들면(1001|0101)은 집합으로 {1001, 0101}을 의미한다. 따라서 (0|1)~은 0과 1로 이루어진 모든 스트링의 집합, 즉 모든 소리의 집합을 말한다. 또 한 예를 보면 (100|11)~은 100과 11을 마음대로 섞어서 만들 수 있는 모든 소리의 집합을 의미한다. 즉 (100|11)~에 해당하는 스트링을 집합으로 나타내면 {100, 11, 10011, 100100100, 1110011, ...}이 된다. 우리가 식별하고자 하는 잠수함의 엔진소리의 패턴은 다음과 같다.

(100~1~|01)~

여기에 속하는 소리의 예를 들어보면, 1001, 01, 100001, 010101, 1000001110101, 1001110101, 0101010101, 10010110000001111101, 01010101011000111, 10000111001111, ...이다.

다시 말해서 이것은 100~1~과 01을 임의로 섞어서 만들 수 있는 모든 스트링의 집합을 나타낸다.

입력으로 0과 1로 구성된 스트링이 주어질 때, 이 스트링이 앞에서 기술된 잠수함의 엔진소리인지 아닌지를 판별하는 프로그램을 작성하라.

입력

0과 1로 구성된 스트링이 1개 들어있다. 이때 각 스트링의 길이는 150개 이하로 제한된다.

출력

입력에 들어있는 스트링을 읽고, 이것이 잠수함의 엔진소리를 나타내는 스트링인지 아니면 그냥 물속의 잡음인지를 판정한 후, 잠수함의 엔진 소리에 해당하는 스트링이면 "SUBMARINE"을 출력하고, 그렇지 않으면 "NOISE"를 출력한다.

예제 입력1

10010111

예제 출력1

NOISE

예제 입력2

100000000001101

예제 출력2

SUBMARINE

백준 2671번 문제

💡Idea

처음에는 문자열을 처음부터 하나씩 읽어가면서, 목표하는 문자열에 부합하는지를 계속해서 확인하는 식으로 접근을 하려 했습니다.

그러다가, 문제에 나와있는 잠수함🚢의 엔진소리의 패턴이 마치 정규식 같다는 생각을 했습니다.

정규표현식(Regular expressions, regex, regexp)이란 문자열의 일정한 패턴을 표현하여, 문자열에서 특정 문자 조합(패턴)을 찾기 위한 언어를 말합니다.

그래서 저는 잠수함 엔진소리의 (100~1~|01)~ 패턴을 정규식으로 표현하여 문제를 해결해보았습니다.

💻코드

• ⏰ 시간 : 136 ms / 메모리 : 33476 KB

import re
import sys
p = re.compile('(100+1+|01)+')
print("SUBMARINE" if p.fullmatch(sys.stdin.readline().strip()) else "NOISE")

📝코드 설명

잠수함 엔진소리인 (100~1~|01)~ 패턴을 정규식으로 변환하여 봅시다!

잠수함 엔진소리는 아래 두 문자열을 임의로 섞어가면서 만들어집니다.

1. 10 + 0 1개 이상 + 1 1개 이상으로 이루어지는 문자열
2. 문자열 01

그리고 위의 문자열을 정규 표현식으로 표현하면 다음과 같습니다.

(100+1+|01)+

📌주의할 점

파이썬에서는 주어진 문자열이 정규 표현식에 매칭이 되는지를 확인하기 위하여 re의 match와 fullmatch 함수를 제공하고 있습니다.

하지만 이 두 함수는 차이점이 있습니다.

1. match : 주어진 문자열이 해당 정규식 패턴으로 시작하는지를 검사
2. fullmatch : 주어진 문자열 전체가 해당 정규식 패턴인지를 검사

예를 들어, 0111은 잠수함의 엔진소리가 아니지만 01로 시작하기 때문에 match를 사용하면 None이 아닌 Match 오브젝트가 반환이 됩니다.

따라서 이 문제에서는 fullmatch를 사용해야 합니다!

Reference

python re match vs full match 에 대해 알아봅시다