문제
풀이
처음에는 string의 substr 함수를 이용해서 제출했지만 결과는 시간 초과였다.
굳이 서브 스트링을 매번 만들어서 비교할 필요 없이 더 간단하고 빠르게 푸는 방법이 있었다.
- 반복문으로 앞에서부터 스트링 S를 확인하며 ‘I’가 나오면 while 문을 통해 IOI가 나올때마다 k에 +1 해준다.
- k == n이 될 때마다 k에 -1 해주고 결과값에 +1 해준다.
이렇게 보면 잘 이해가 안 될 수 있으니 코드를 통해 확인해보자.
소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <string>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, m;
cin >> n >> m;
string s;
cin >> s;
int ans = 0;
for (int i = 0; i < m; i++)
{
int k = 0; // k는 IOI의 길이. IOI면 1 , IOIOI면 2
// O가 나오면 pass
if (s[i] == 'O')
continue;
// s[i] == 'I'일 때
else
{
while (s[i + 1] == 'O' && s[i + 2] == 'I')
{
k++;
if (k == n)
{
k--; // 중복 카운트를 막기 위해 -1 해준다.
ans++;
}
i += 2; // O를 건너 뛴다.
}
k = 0;
}
}
cout << ans;
return 0;
}
