백준 2671 잠수함식별 Kotlin (문자열)

문제 출처 : https://www.acmicpc.net/problem/2671

2671번: 잠수함식별

문제

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

우리는 물속에서 들리는 소리의 패턴을 듣고서 그 소리가 특정한 잠수함에서 나오는 소리인지 아닌지를 알아내려고 한다. 이 문제에서는 잠수함의 소리가 두 종류의 단위 소리의 연속으로 이루어져 있고, 그 단위 소리를 각각 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"를 출력한다.

알고리즘 분류

• 문자열
• 정규 표현식

풀이

오늘 본 코테에 입력 데이터만 달랐지, 완전히 같은 유형의 문제가 나왔다.

50분 동안 빡구현했는데 결국 틀렸다.

이후 얘길 들어보니 정규 표현식으로 하면 몇 십줄로 끝낼 수 있는 문제라 한다.

킹받는다... 정규 표현식 모르는데...

그래도 어찌어찌 할 수 있을 것만 같은 느낌이었는데,

dfa? 오토마타? 라는 알고리즘을 구현하면 된다고 한다.

모르겠다 그냥 구현하면 될 거 같다고 생각했기에 다시 구현해보았고, 코테 문제도 맞는 풀이를 찾을 수 있었고,

이 잠수함식별 문제도 맞을 수 있었다.

 

우선 두 가지 패턴이 있다.

01

100~1~

 

0으로 시작하는 패턴은 다음에 1이 무조건 나와야 한다.

1로 시작하는 패턴은 다음에 00이 무조건 나와야 하고, 0~이후 1이 무조건 나와야 한다.

 

0으로 시작하는 패턴은 간단하다.

str[i]이 0으로 시작하고, 현재 0으로 시작하는 패턴이라고 하면 

i+1이 str길이를 넘어가지 않고, str[i+1]이 1이라면 01패턴을 만족하니 i에 2를 추가한다.

 

이후 다시 i가 0으로 시작하는 패턴인지 1로 시작하는 패턴인지 검사한다.

1로 시작하는 패턴이라면,

최소 1001이 나와야 하기 때문에, i+3이 str길이를 넘어가지 않고, str[i+1], str[i+2] 이 0이어야 한다.

위 조건을 만족한다면 i에 3을 추가한다.

현재 i는 100~1~ 에서 첫 번째 ~에 위치하게 된다.

따라서 ~에서 나오는 0000을 모두 스킵하고 1~로 넘어간다.

1이 나온다면 1 이후의 ~에서 나오는 11111을 모두 스킵한다.

다만, 1001001같은 입력도 있기 때문에, i+2가 str의 길이를 넘어가지 않고, str[i+1], str[i+2]가 0인 경우 다시 1로 시작하는 패턴의 처음부터 검사해주자.

 

아래 문제는 완전히 동일한 문제이다.

정답만 여러 번 출력하면 된다.
https://www.acmicpc.net/problem/1013

1013번: Contact

 

참고 풀이 : https://travelbeeee.tistory.com/431

코드

//100~1~
//01
fun dfa(str : String) : Boolean{
    var i = 0
    while(i<str.length){
//        println("$i ${str[i]}")
        //0으로 시작하는 패턴
        if(str[i]=='0'){
            if(i+1>=str.length) return false
            if(str[i+1]!='1') return false
            i+=2
        }
        //1로 시작하는 패턴
        else{
            if(i+3>=str.length) return false
            if(str[i+1]!='0' || str[i+2]!='0') return false
            i+=3
            while(i<str.length && str[i]=='0'){
                i++
            }
            //0만 이어지다가 1은 안 나오고 끝난 경우
            if(i>=str.length) return false
            i++
            while(i<str.length && str[i]=='1'){
                if(i+2<str.length && str[i+1]=='0' && str[i+2]=='0') break
                i++
            }

        }

    }
    return true
}

fun main() = with(System.out.bufferedWriter()) {
    val br = System.`in`.bufferedReader()
    val str = br.readLine()
    if(dfa(str)){
        write("SUBMARINE")
    }
    else {
        write("NOISE")
    }
    close()
}