문자열 일치 수를 확인하는 문제이다.
매번 일치 여부를 확인하면 O(n^2)이 되므로 tle가 발생할 것이다.
따라서 1번의 문자열 탐색으로 답을 도출한다.
내가 푼 첫 번째 방법은 이렇다.
1. ioio 정상적으로 문자열이 진행된다
=> bool flag만 바꿔주어 i=true일때는 I가, false일 때는 O가 나오는지 체크한다.
2. 문자열이 끊겼다.
2-1. 첫 시작이 O이거나 OO로 끝났다
=> start와 end 모두 현재 위치의 다음 문자를 탐색한다.
2-2. II로 끝났다
=> start는 현재위치에 두고 다음 문자를 탐색한다.
2-3. 길이 구하기
=> len = end - start를 한 후 2*n+1과 비교한다.
if len < 2*n+1 이라면 패스
그렇지 않다면 (len+1)/2 : 1의 개수 - n: 찾고자 하는 Pn에서 1의 개수를 통해
Pn이 몇 번 반복되는지 확인한다.
** 주의: 배열을 선형탐색 + 매번 조건을 확인하는 것이 아니라 특정 시점에서만 조건을 확인한다면
-> 모든 탐색이 끝난 후 한번 더 조건을 확인해주어야 한다.
1
5
IOIOI 같은 경우엔 마지막 I까지 길이 체크를 하지 않으므로 마지막 확인 작업이 꼭 필요하다.
#include <stdio.h>
using namespace std;
int n, m;
char str[1000001];
int main(void)
{
scanf("%d%d", &n, &m);
scanf("%s", str);
int res = 0, len = 0, start = 0, end = 0;
bool i = true;
bool ing = false;
for (; end < m; end++)
{
if (i && str[end] == 'I')
{
i = false;
}
else if (!i && str[end] == 'O')
{
i = true;
}
else
{
len = end - start;
if (str[end] == 'O')
{
i = true;
start = end + 1;
}
else
{
i = false;
start = end;
}
if (len < 2 * n + 1)
continue;
res += (len + 1) / 2 - n;
}
}
len = end - start;
if (len >= 2 * n + 1)
{
res += (len + 1) / 2 - n;
}
printf("%d\n", res);
return 0;
}
또 다른 풀이:
O의 개수만 확인하는 방법이다.
1. IOI를 만족한다면 O의 개수를 늘림
1-1. IF 여태 찾은 O의 개수== n THEN answer++
다음 IOI 구간을 확인하기 위해 O의 개수를 하나 줄인다.
2. IOI를 만족하지 않으면 O의 개수를 0으로 초기화
#include <stdio.h>
using namespace std;
int n, m;
char str[1000001];
int main(void)
{
scanf("%d%d", &n, &m);
scanf("%s", str);
int res = 0, o_num = 0;
for (int i = 0; i < m - 2; i++)
{
if (str[i] == 'I' && str[i + 1] == 'O' && str[i + 2] == 'I')
{
o_num++;
if (o_num == n)
{
res++;
o_num -= 1;
}
i++;
}
else
{
o_num = 0;
}
}
printf("%d\n", res);
return 0;
}
'알고리즘 문제풀이 > 백준' 카테고리의 다른 글
[백준 1790] 수 이어쓰기2 (0) | 2021.02.01 |
---|---|
[백준 9205] 맥주 마시면서 걸어가기 (0) | 2021.01.31 |
[백준 1620] 나는야 포켓몬 마스터 이다솜 (0) | 2021.01.31 |
[백준 1043] 거짓말 (0) | 2021.01.30 |
[백준 11660] 구간 합 구하기 5 (0) | 2021.01.28 |
댓글