baekjoon 5525:IOIOI

baekjoon 5525 IOIOI

5525번 IOIOI

접근

서브태스크가 있는 걸로 봐서 최적의 알고리즘을 만들지 않으면 100점 통과하지 못하지 않을까 싶었다.
S에 있는 원소들을 여러번 확인하는 것은 비효율이 발생한다.
최소로 생각해보면 딱 한번씩만 확인해서 O(M)에 끝내는게 바람직한다. 만약 길이 2n+1을 확인했는데 맞다면, 그다음 2칸만 확인하고
중간에 틀렸다면 그 틀린 부분 이후로 확인해야 비효율이 발생하지 않는다.

코드

#include <iostream>
#include <string>
#include <vector>
using namespace std;
void check(string &ss, int &count, int &n, int start_idx);
void checkSlide(string &ss, int &count, int &n, int start_idx);
int main() {
  int n, m;
  cin >> n >> m;
  vector<bool> s(m);
  string ss;
  cin >> ss;
  int count = 0;
  check(ss, count, n, 0);
  cout << count;

  return 0;
}
void check(string &ss, int &count, int &n, int start_idx) {
  if (start_idx > ss.length() - 1 - 2 * n) {
    return;
  }
  bool res = true;
  for (int i = 0; i < n; i++) {
    if (ss[start_idx + i * 2] != 'I' || ss[start_idx + i * 2 + 1] != 'O') {
      res = false;
      check(ss, count, n, start_idx + i * 2 + 1);
      return;
    }
  }
  if (ss[start_idx + n * 2] != 'I') {
    res = false;
    check(ss, count, n, start_idx + n * 2 + 1);
    return;
  }
  if (res) {
    count++;
    checkSlide(ss, count, n, start_idx + 2);
    return;
  }
}
void checkSlide(string &ss, int &count, int &n, int start_idx) {
  if (start_idx > ss.length() - 1 - 2 * n) {
    return;
  }
  if (ss[2 * n + start_idx - 1] == 'O' && ss[2 * n + start_idx] == 'I') {
    count++;
    checkSlide(ss, count, n, start_idx + 2);
    return;
  } else {
    check(ss, count, n, start_idx + 2 * n - 1);
    return;
  }
}

배운 점

비효율을 줄이자.