문제 링크: 5525번: IOIOI
1. Code
#include <iostream>
#include <string>
int main()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
// 입력
int N, M;
std::cin >> N >> M;
std::string S;
S.reserve(M);
std::cin >> S;
int answer = 0;
int count = 0;
// Pn을 탐색
for (int i = 0; i < M - 2;)
{
if ((S[i] == 'I') && (S[i + 1] == 'O') && (S[i + 2] == 'I'))
{
++count;
// Pn을 포함하고 있는 경우
if (count >= N)
{
++answer;
}
i += 2;
}
else
{
count = 0;
++i;
}
}
std::cout << answer;
return 0;
}
C++
복사
2. Review
처음엔 슬라이딩 윈도우 방식으로 접근 했습니다. Pn을 포함하는지 검사할 때 Pn의 모든 문자열을 비교했습니다. 그런 방식으로 코드를 작성했을 때 N, M의 제약 조건이 없는 서브태스크에서 시간 초과가 났습니다. 이 방식은 O(M * N)의 시간 복잡도 였습니다. 시간 초과가 나지 않게 만들기 위해 O(M) 시간 복잡도 알고리즘으로 최적화 했습니다. Pn을 포함하는지 확인할 때, Pn의 모든 문자열을 검사하는 방식이 아니라 연속되는 IOI 문자열이 있을 때마다 IOI 문자열의 개수를 세는 방식을 사용합니다. 연속되는 IOI의 개수가 N 이상이면, Pn을 포함한다고 판단할 수 있습니다. 이렇게 최적화 했을 때, 8ms로 모든 서브태스크를 통과했습니다.