[백준 5525] IOIOI

www.acmicpc.net/problem/5525

5525번: IOIOI

문자열 일치 수를 확인하는 문제이다.

매번 일치 여부를 확인하면 O(n^2)이 되므로 tle가 발생할 것이다.

따라서 1번의 문자열 탐색으로 답을 도출한다.

 

내가 푼 첫 번째 방법은 이렇다.

1. ioio 정상적으로 문자열이 진행된다 

=> bool flag만 바꿔주어 i=true일때는 I가, false일 때는 O가 나오는지 체크한다. 

2. 문자열이 끊겼다.

2-1. 첫 시작이 O이거나  OO로 끝났다

=> start와 end 모두 현재 위치의 다음 문자를 탐색한다.

2-2. II로 끝났다

=> start는 현재위치에 두고 다음 문자를 탐색한다.

2-3. 길이 구하기

=> len = end - start를 한 후 2*n+1과 비교한다.

if len < 2*n+1 이라면 패스

그렇지 않다면 (len+1)/2 : 1의 개수 - n: 찾고자 하는 Pn에서 1의 개수를 통해 

Pn이 몇 번 반복되는지 확인한다.

 

** 주의: 배열을 선형탐색 + 매번 조건을 확인하는 것이 아니라 특정 시점에서만 조건을 확인한다면

-> 모든 탐색이 끝난 후 한번 더 조건을 확인해주어야 한다.

1

5

IOIOI 같은 경우엔 마지막 I까지 길이 체크를 하지 않으므로 마지막 확인 작업이 꼭 필요하다.

#include <stdio.h>

using namespace std;
int n, m;
char str[1000001];
int main(void)
{
  scanf("%d%d", &n, &m);
  scanf("%s", str);
  int res = 0, len = 0, start = 0, end = 0;
  bool i = true;
  bool ing = false;
  for (; end < m; end++)
  {
    if (i && str[end] == 'I')
    {
      i = false;
    }
    else if (!i && str[end] == 'O')
    {
      i = true;
    }
    else
    {
      len = end - start;

      if (str[end] == 'O')
      {
        i = true;
        start = end + 1;
      }
      else
      {
        i = false;
        start = end;
      }
      if (len < 2 * n + 1)
        continue;
      res += (len + 1) / 2 - n;
    }
  }
  len = end - start;
  if (len >= 2 * n + 1)
  {
    res += (len + 1) / 2 - n;
  }
  printf("%d\n", res);
  return 0;
}

 

또 다른 풀이:

O의 개수만 확인하는 방법이다. 

1. IOI를 만족한다면 O의 개수를 늘림

1-1. IF 여태 찾은 O의 개수== n THEN answer++

다음 IOI 구간을 확인하기 위해 O의 개수를 하나 줄인다.

2. IOI를 만족하지 않으면 O의 개수를 0으로 초기화

#include <stdio.h>

using namespace std;
int n, m;
char str[1000001];
int main(void)
{
  scanf("%d%d", &n, &m);
  scanf("%s", str);
  int res = 0, o_num = 0;
  for (int i = 0; i < m - 2; i++)
  {
    if (str[i] == 'I' && str[i + 1] == 'O' && str[i + 2] == 'I')
    {
      o_num++;
      if (o_num == n)
      {
        res++;
        o_num -= 1;
      }
      i++;
    }
    else
    {
      o_num = 0;
    }
  }

  printf("%d\n", res);
  return 0;
}