백준 5525 IOIOI

https://www.acmicpc.net/problem/5525

문제와 채점은 위 사이트에서 확인 하실 수 있습니다.

 

이 문제는 입력 받은 문자열과 N,M을 통해 I와 N개의OI가 연속한 문자가 몇개 있는지 찾는 문제입니다.

 

입력이 백만까지 주어져있으므로 단순 비교로는 시간초과가 나올 것입니다. 따라서 저는 OI의 개수를 세어서 Pn을 만족하는 문자열이 나오면

개수를 하나 증가시키고 OI의 개수를 하나 줄인뒤 다시 뒤에 2개의 값을 비교해서 OI가 또 다시 나온다면 개수를 증가 시키는 방식으로 해결 하였습니다.

 

예를 들어 IOIOI가 몇개 있는지 찾아야 한다고 할때 주어진 문장이 IIOIOIOIOIII 이런식이라면 처음에 IOIOI를 발견 했을 때 개수를 하나 증가시키고 OI의 개수를 하나 감소 시키면 가장 앞에 있는 IO는 없다고 생각하고 뒤의 OI를 찾아서 있으면 개수를 하나 증가시키는 방식으로 끝의 OI를 제외한 나머지 부분을 탐색하지 않고 그대로 이용해서 시간을 줄일 수 있습니다.

 

다음은 코드입니다.

 

#include <iostream>
#include <string> 

using namespace std;

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int N,M;
	string s;
	
	cin >> N >> M >> s;
	int num = 0;
	
	for(int i = 0; i < M; i++) {
		if(s[i] == 'I' && s[i+1] == 'O'){ //i번째 와 i+1번째 인덱스가 IO인지 확인 
			int On = 0;
			while(s[i+1] == 'O' && s[i+2] == 'I'){ //i+1번째와 i+2 번째 인덱스가 OI 이면 On과 i를 증가시키며 반복 
				i+=2;
				On++;
				if(s[i] == 'I' && On == N)	 { //On과 N이 같으면 num을 증가하고 On은 한개 감소시킴  
					On--;
					num++;
				}
			}
		}
	}
	
	cout<< num;
	return 0;
}