[백준 5525] IOIOI

문제설명

알고리즘

<50점>

1. 입력받기

2. N으로 패턴 만들기

3. 주어진 문자열 S에서 N을 find함수로 찾기

4. 찾을때 마다 결과값 변수 1씩 증가, index를 업데이트

<100점>

1. 입력받기

2. I를 만날때 마다 바로 뒤에 OI가 있으면 k증가, 문자열 index를 2씩 증가

3. OI가 I이후로 N번 나오면 패턴 매칭이 완료된 것이므로 결과 값 증가 , k 감소

4. 결과값 출력

코드

#include<iostream>
#include<string>

using namespace std;

int main() {
	int N, M,cnt=0;
	cin >> N >> M;

	string S;
	cin >> S;

	/*string val;
	for (int i = 1; i <= 2 * N + 1; i++)//패턴 생성
	{
		if (i % 2 == 0)
			val += 'O';
		else
			val += 'I';
	}

	for (int i = 0; i < M; i++)//다음 값 탐색
	{
		if (S.find(val, i)!=-1) {//문자열을 찾지 못한 경우가 아니면 
			i = S.find(val, i);//문자열 찾은 곳 저장
			cnt++;//결과 값 증가
		}
	}*/

	for (int i = 0; i < M; i++)
	{
		int k = 0;//패턴 수를 세기 위한 변수 
		if (S[i] == 'I') {
			while (S[i + 1] == 'O' && S[i + 2] == 'I') {
					k++;//IOI한번 발견 
					if (k == N)//IOI가 n번 발견된 경우 
					{
						k--;
						cnt++;
					}
					i += 2;
			}
			k = 0;
		}
	}

	cout << cnt;
	return 0;
}

이번 문제는 서브태스크가 존재하는 문제여서 50점, 100점 둘다 나왔다

주석으로 처리된 부분이 50점을 받았던 알고리즘이다

고찰

문자열을 토픽으로 한 문제였는데, find함수를 사용해서 했더니 50점을 맞았다

직접 계산하는 방식으로 바꾸니까 통과했는데 왜 더 빠른지는 잘 모르겠다 

아무래도 find 함수에 대한 이해가 부족 해서 그런거같다