[백준] IOIOI (5525번)

문제

N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다.

• P1 IOI
• P2 IOIOI
• P3 IOIOIOI
• PN IOIOI...OI (O가 N개)

I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 군데 포함되어 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다. (1 ≤ N ≤ 1,000,000, 2N+1 ≤ M ≤ 1,000,000)

출력

S에 PN이 몇 군데 포함되어 있는지 출력한다.

예제 입력 1 복사

1 13 OOIOIOIOIIOII

예제 출력 1 복사

4

---

문자열 처리 문제이다.

문제를 처음에 잘 못 읽어서 문자열 S에 포함된 모든 P_N을 구하는 줄 알고 IOI, IOIOI, IOIOIOI 각각을 포함하는 개수를 다 구했는데 단지 저 중에 하나만 몇 개를 포함하는지 구하면 된다.

string find 함수를 이용해서 문제를 풀다가 시간초과가 떴다.

그냥 처음부터 for문으로 문자열을 일일이 검사하자.

S[i]가 O면 건너가고 I일때 S[i+1]과 S[i+2]가 OI인 경우 검사를 더 한다.

O의 개수가 N과 같아질때까지 while 문을 통해 길이를 늘린 후 N과 O의 개수가 같아지면 결과값을 하나 추가한다.

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/IOIOI%20(5525%EB%B2%88).cpp

chosh95/STUDY

C++ 코드

#include <iostream>
#include <string>
using namespace std;

int N, M, res;
string S;

int main()
{
	cin >> N >> M >> S;

	for (int i = 0; i < M; i++) {
		if (S[i] == 'O') continue;
		int oCnt = 0;
		while (S[i + 1] == 'O' && S[i + 2] == 'I') {
			oCnt++;
			i += 2;
			if (oCnt == N) {
				oCnt--;
				res++;
			}
		}
	}

	cout << res;
}