[BOJ] 백준 2671번 잠수함식별 (Python)

deannn.Park·2021년 10월 2일

algorithm boj python 문자열 백준 코딩테스트

BOJ - 백준

목록 보기

37/42

BOJ: Q2671 - 잠수함식별 [ 골드 5 ]

문제

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

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

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

1~ = {1, 11, 111, 1111, ..., 1...1, ...}
(01)~ = {01, 0101, 010101, 01010101. ...}
0 (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

풀이


input_string = str(input())		# 입력

N = len(input_string)			# 소리 길이
# 소리가 1인 위치 저장
splitter = [i for i in range(N) if input_string[i] == '1']
isSubmarine = False			# 신호 여부
last = -1				# 직전 신호 확인용

if input_string[:2] == '01':		# 맨 처음 수 2개가 '01'이면
    last = 2				# 신호: 2
    
for i in range(1, len(splitter)):	# 1의 위치 기준으로 반복문 실행
    # 1의 위치 기준으로 문자열 자름. 앞쪽 1 제외 뒷쪽 1 포함.
    s_slice = input_string[splitter[i-1] + 1:splitter[i] + 1]
    # 자른 문자열이 '01'이거나 첫 문자열인 경우
    if s_slice == '01' and last != -1:	
        last = 2			# 직전 패턴이 2라 하고 
        continue			# 다음 반복문 실행

    # 1의 위치 기준으로 문자열 자름. 앞쪽 1 포함 뒷쪽 1 포함.
    s_slice = input_string[splitter[i-1]:splitter[i] + 1]
    
    # 자른 문자열이 '11'이고 
    # 직전 패턴이 '100~1~'(1 or 11)이거나 자른 문자열 앞뒤로 '0'이 있을 경우
    # '11' 앞뒤로 '0'이 있는 경우는 1번 패턴 -> 2번 패턴이거나 그 반대인 경우와 1번 패턴 -> 1번 패턴 뿐이다.
    # 2->1 인지는 다음에 판단. 일단 1 -> 1 or 1 -> 2이라고 가정.
    if s_slice == '11' and (last == 1 or last == 11 or (input_string[splitter[i-1]-1:splitter[i]+2] == '0110')):
        last = 11			# 1번 패턴의 마지막임을 알리는 표시
        continue
     
    s_size = len(s_slice)		# 자른 문자열의 길이
    
    if s_size >= 4:			# 자른 문자열의 길이가 4가 넘으면 1번 패턴인지 확인
        # 1번 패턴이라면 자른 문자열은 아래와 같은 문자열이어야 한다.
        s_compare = '100' + ('0' * (len(s_slice) - 4)) + '1'
        if s_slice == s_compare: 	# 비교 후 같다면
            last = 1			# 직전 패턴을 1로 수정
            # 만약 현재 문자열 앞 숫자가 0이라면 소음.
            # 1번 패턴과 2번 패턴 모두 1로 끝남.
            if input_string[splitter[i-1]-1] == '0':
                break
    else:	
        # 문자열 길이가 4보다 작고 '01'도 아니기에 소음이다.
        break
else:
    # 위의 과정을 모두 통과하면 신호이다.
    isSubmarine = True

# 특수한 경우 처리
if input_string[0] == '0' and (N == 1 or (N >= 2 and input_string[:2] != '01')):
    # 길이가 짧거나, 0으로 시작하는데 2번째 수가 1이 아닌 경우
    isSubmarine = False
elif input_string[0] == '1' and N < 4:
    # 1로 시작하는데 길이가 4보다 작은 경우
    isSubmarine = False
elif input_string[-1] == '0':
    # 소리의 끝맺음이 없는 경우
    isSubmarine = False


if isSubmarine:
    print("SUBMARINE")
else:
    print("NOISE")