문제
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 | 추가적인 제약 조건이 없다. |
예제 입력 1
1
13
OOIOIOIOIIOII
예제 출력 1
4
OOIOIOIOIIOIIOOIOIOIOIIOIIOOIOIOIOIIOIIOOIOIOIOIIOII
예제 입력 2
2
13
OOIOIOIOIIOII
예제 출력 2
2
OOIOIOIOIIOIIOOIOIOIOIIOII
#include <iostream>
#include <stack>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int N, M, result = 0;
stack<char> stackTemp;
char temp;
cin >> N >> M;
for (int i = 0; i < M; i++)
{
cin >> temp;
if (stackTemp.empty())
{
if (temp == 'I')
{
stackTemp.push(temp);
}
}
else
{
if (stackTemp.top() != temp)
{
stackTemp.push(temp);
}
else
{
if (stackTemp.top() != 'I')
{
stackTemp.pop();
}
int temp1 = ((stackTemp.size() - 1) / 2 - (N - 1));
if (temp1 > 0)
{
result += temp1;
}
while (!stackTemp.empty())stackTemp.pop();
if (temp == 'I')
{
stackTemp.push(temp);
}
}
}
}
if (!stackTemp.empty())
{
if (stackTemp.top() != 'I')
{
stackTemp.pop();
}
int temp1 = ((stackTemp.size() - 1) / 2 - (N - 1));
if (temp1 > 0)
{
result += temp1;
}
while (!stackTemp.empty())stackTemp.pop();
}
cout << result;
return 0;
}728x90
반응형
'알고리즘 > solved.ac' 카테고리의 다른 글
| [class3] (백준 11279) 최대 힙 (0) | 2021.11.19 |
|---|---|
| [class3] (백준 11047) 동전 0 (0) | 2021.11.18 |
| [class3] (백준 1931) 회의실 배정 (0) | 2021.11.16 |
| [class3] (백준 1780) 종이의 개수 (0) | 2021.11.15 |
| [class3] (백준 1541) 잃어버린 괄호 (0) | 2021.11.14 |