[백준] 5525번 - IOIOI (C++)

5525번: IOIOI

 

 

문제

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가 주어진다.

 

 

출력

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

 

 

제한

• 1 ≤ N ≤ 1,000,000
• 2N+1 ≤ M ≤ 1,000,000
• S는 I와 O로만 이루어져 있다.

 

 

서브태스크

번호배점제한

1	50	N ≤ 100, M ≤ 10 000.
2	50	추가적인 제약 조건이 없다.

 

 

 

풀이과정

이 문제는 정말 다방면으로 접근을 해봤던 거 같다.

문제에서 원하는 요구사항이 s(문자열)안에 내가 원하는 문자열이 있는지 확인해야하는 문제이다보니 

하나하나씩 다 대입해보는 방식과 KMP라고 불리는 방식 모두를 사용해보았었다.

 

1. 처음에는 하나하나씩 다 확인하는 방식

2. KMP라고 불리는 문자열 검색알고리즘 사용

1번 방법같은 경우는 시간이 오래걸리니 시간초과가 될거라는건 알고 있었지만

2번 방법까지 시간이 넘어설거리는거는 생각하지못하였다.

 

그래서 알아낸 방법이

3. S문자열 1번만 도는 방법

을 사용해서 해결하였다. 문제에서 주어지는 문자열 자체가  "IOI..." 형식으로 반복이 되다보니

그점을 사용하여 알고리즘 풀이를 만들어내었다.

code

#include <iostream>
#include <string>

int		main(void)
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);

	int n, m, count, k;
	std::string str;
	
	std::cin >> n >> m >> str;
	count = 0;
	for (int i = 0; i < m; i++) {
		if (str[i] == 'I') {
			k = 0;
			while (str[i + 1] == 'O' && str[i + 2] == 'I')
			{
				k++;
				if (k == n) {
					k--;
					count++;
				}
				i += 2;
			}
		}
	}
	std::cout << count << "\n";

	return (0);
}

 

후기

고생해서 KMP라는 알고리즘을 공부하고 문제해결에 대입까지 했었는데

KMP조차 시간초과가 나니 약간 허무해졌던 문제같다.

3번같이 간단하게 푸는 방법이 있었다니..