BOJ 2671

13 Apr 2020 • ProblemSolving

잠수함 식별

문제출처

문제 해석

  • 잠수함 엔진소리의 패턴인지 맞추는 문제입니다.
  • 한 특정한 소리의 반복은 ~로 표시합니다.
  • (x y)는 x 또는 y중에서 아무거나 하나만 선택해서 만든 소리의 집합입니다.
  • “(100~1 01)~“에 속하는 소리인지 맞추면 됩니다.

설계(20)

  • 문자열 처리 문제입니다
  • 처음에 문제를 어떻게 구현해야할 지 생각을 오래하였습니다.
  • 결국 naive하게 재귀형태로 구현하였습니다.
  • 먼저, “100”으로 시작하는 패턴과 “01”로 시작하는 패턴 두개로 구분하여 따로 구현해줍니다.
  • 나머지의 경우는 모두 false처리해줍니다.
  • “100”의 경우에 0이 반복되고 1이 반복되는지 체크합니다.
  • 여기서, 주의할 점은 “10011001”의 패턴의 경우에 다음 0부터 시작하여 정답인 SUBMARINE이 아닌 NOISE가 나오게 됩니다.
  • 따라서 다음 체크할 패턴이 100의 패턴에 해당하는지 구분해서 리턴해줄 필요가 있습니다.
  • 두번째 “01”의 경우에는 바로 다음 재귀문으로 리턴해줍니다.

구현(60)

코드
#include <iostream>
#include <string>
using namespace std;
string s;
bool go(string s) {
    int N = s.length();
    if (N == 0) return true;
    if (N >= 4 && s[0] == '1' && s[1] == '0' && s[2] == '0') {
        int idx = 2;
        while (idx < N && s[idx] == '0') {
            idx++;
        };
        if (idx == N) return false;
        while (idx < N && s[idx] == '1') {
            idx++;
        };
        if (idx + 1 < N && s[idx] == '0' && s[idx + 1] == '0' && s[idx-2] =='1') return go(s.substr(idx - 1));
        else return go(s.substr(idx));
    }
    if (N >= 2 && s[0] == '0' && s[1] == '1') {
        return go(s.substr(2));
    }
    return false;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> s;
    bool ans = go(s);
    if (ans) cout << "SUBMARINE\n";
    else cout << "NOISE\n";
    return 0;
}
디버깅
  • 반례를 찾는데 오래걸렸습니다.
  • “100”패턴을 체크한 후, 다음 패턴을 찾을 때 s[idx]와 s[idx+1]만 체크하는 실수를 하였습니다.
  • 이럴 경우에 “1001001”또한 정답으로 되는 것을 깨달았습니다.
  • 따라서 s[idx-2]가 1인지 체크해주어야합니다.
제출결과
  • 0 ms

마무리

  • 문자열 처리문제였습니다. 솔루션을 보니 정규식으로 쉽게 처리가 가능한 것을 보았습니다.
  • 그러나, 정규식 stl문을 사용하지 않아도 충분히 재귀함수로 구현이 가능했습니다.
 BOJ

Related Posts