[백준 5525] IOIOI (C#, C++) - soo:bak

문제 링크

5525번 - IOIOI

설명

P_N은 I로 시작하여 OI가 N번 반복되는 패턴입니다.

예를 들어 P_1 = IOI, P_2 = IOIOI, P_3 = IOIOIOI입니다.

문자열 S가 주어질 때, P_N이 S에 몇 번 등장하는지 구하는 문제입니다. 겹쳐서 등장하는 경우도 모두 세어야 합니다.

접근법

문자열을 한 번만 순회하며 연속된 IOI 패턴의 개수를 세어 해결합니다.

문자열의 각 위치에서 IOI 패턴을 확인합니다.

IOI를 찾으면 카운트를 증가시키고 인덱스를 2만큼 증가시킵니다. 이렇게 하면 겹치는 부분을 효율적으로 탐색할 수 있습니다.

카운트가 N 이상이 되면 답을 증가시킵니다.

예를 들어 IOIOIOI에서는 연속된 IOI가 3개이므로 P_1이 3번, P_2가 2번 나타납니다.

IOI 패턴을 찾지 못하면 카운트를 0으로 초기화하고 인덱스를 1만큼 증가시켜 다음 위치를 탐색합니다.

---

Code

C#

using System;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      var n = int.Parse(Console.ReadLine()!);
      var m = int.Parse(Console.ReadLine()!);
      var s = Console.ReadLine()!;

      var answer = 0;
      var count = 0;

      for (var i = 1; i < m - 1; ) {
        if (s[i - 1] == 'I' && s[i] == 'O' && s[i + 1] == 'I') {
          count++;
          if (count >= n)
            answer++;
          i += 2;
        } else {
          count = 0;
          i++;
        }
      }

      Console.WriteLine(answer);
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m; cin >> n >> m;
  string s; cin >> s;

  int answer = 0, count = 0;

  for (int i = 1; i < m - 1; ) {
    if (s[i - 1] == 'I' && s[i] == 'O' && s[i + 1] == 'I') {
      ++count;
      if (count >= n)
        ++answer;
      i += 2;
    } else {
      count = 0;
      ++i;
    }
  }

  cout << answer << "\n";

  return 0;
}