문제

2671번: 잠수함 식별

풀이

문자열이 올바른 패턴에 맞는지 확인하는 구현 문제이다.

패턴이 반복되기 때문에 한 패턴이 올바른지 확인 후 다음 패턴으로 넘어가기 위해 재귀함수를 활용해서 해결했다.
문자열의 인덱스를 파라미터로 하여 재귀함수를 호출했는데, 이때 인덱스가 문자열의 크기를 넘어가는지 항상 확인하는 것이 문제였다.
또한 100~1~ 패턴이 예를 들어 1000111로 끝난다면 이 문자열의 끝이 6번 인덱스일때, 5번 인덱스일때 두 가지 경우 모두 확인해야 했다.

코드

#include <iostream>
#include <string>
#include <vector>

using namespace std;

string input;

bool check(int idx){
    if (input[idx] == '0'){ // 01
        if (input[idx+1] == '1') {
            if (idx+2 < input.size()){
                return check(idx+2); // true;
            }
            else {
                return true;
            }
        }
        else{
            return false;
        }
    }
    else { //if(input[idx] == '1'){ // 100~1~
        if (input[idx+1] == '0' && input[idx+2] == '0'){
            int i=2;
            int j=0;
            while(input[idx+i] == '0'){
                i++;
            } // input[idx+i] == '1'혹은 배열 밖의 인덱스
            if (idx+i >= input.size()) return false;
            
            while(input[idx+i+j] == '1'){
                j++;
            } // input[idx+i+j] == '0' 혹은 배열 밖의 인덱스
            if (idx+i+j >= input.size()) { // 1로 문자열이 끝남
                return true;
            }
            else if (input[idx+i+j-2] == '0') { // j < 1, 01로 패턴 종료
                return check(idx+i+j);
            }
            else {
                return check(idx+i+j) || check(idx+i+j-1);
            }
        }
        else {
            return false;
        }
    }
}

int main() {
    cin >> input;

    if (check(0)) {
        cout << "SUBMARINE" << endl;
    }
    else {
        cout << "NOISE" << endl;
    }

    return 0;
}