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이 몇 군데 포함되어 있는지 출력한다.
문제풀이
처음에 KMP 알고리즘을 사용해야 하나? 라는 생각이 들었지만 아무래도 난이도가 높은 문제가 아니었기 때문에 다시 차근차근 생각해 봤다.
사용되는 문자열이 두 개밖에 없고, 제한사항을 보아 이건 리니어한 방법으로 풀어야 한다고 생각했다.
맨 처음 문자열 길이만큼의 배열을 만들어 준다.
첫 문자가 I일 경우 배열에 1을, O일 경우 0을 넣는다.
두 번째 문자부터는 반복문을 돌린다.
4가지 경우로 나눌 수 있다. 우리는 Pn을 만드는 것이 목적이다.
1. 이전 것이 O이고 지금 것이 I인 경우 -> 이전 것 배열의 값에 1을 더해 지금 것 배열 인덱스에 넣어준다.
2. 이전 것이 O이고 지금 것도 O인 경우 -> 지금 것 배열 인덱스에 0을 넣어준다.
3. 이전 것이 I이고 지금 것이 O인 경우 -> 이전 것 배열의 값에 1을 더해 지금 것 배열 인덱스에 넣어준다.
4. 이전 것이 I이고 지금 것도 I인 경우 -> 지금 것 배열 인덱스에 1을 넣어준다.
이렇게 하면 배열에 숫자들이 저장되는데 이 숫자들의 의미는 바로 IO가 올바르게 반복된 숫자이다.
즉 IOI 인경우 마지막 배열엔 3이 저장되고, IOIO인 경우 4가 저장되고, 이런 식이다.
그렇기 때문에 Pn의 값인 3 + 2*(n-1) 보다 크거나 같은 경우는 Pn을 만들 수 있다는 말이 된다.
마지막으로 반복문을 처음부터 다시 돌면서 3 + 2*(n-1) 보다 크거나 같고, I인 경우만 answer을 1씩 더해주면 된다.
#include <iostream>
#include <string>
using namespace std;
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n, m;
string s;
cin >> n >> m >> s;
int arr[s.size()];
if(s[0] == 'I')
arr[0] = 1;
else
arr[0] = 0;
for(int i=1; i<s.size(); i++) {
if(s[i] == 'I' && s[i-1] == 'O') {
arr[i] = arr[i-1] + 1;
}
else if(s[i] == 'I') {
arr[i] = 1;
}
else if(s[i] == 'O' && s[i-1] == 'I') {
arr[i] = arr[i-1] + 1;
}
else {
arr[i] = 0;
}
}
int check = 3 + 2*(n-1);
int answer = 0;
for(int i=0; i<s.size(); i++) {
if(check <= arr[i] && s[i] == 'I')
answer++;
}
cout << answer;
return 0;
}
나는 -1 만 확인하는 방식으로 했는데 -1, -2 번째 인덱스까지 확인하는 방법으로 풀이해도 된다. 그게 좀 더 빠른 듯?
'알고리즘(Algorithm)' 카테고리의 다른 글
[C++] 적록색약 (10026번) (0) | 2022.12.02 |
---|---|
[C++] 테트로미노 (14500번) (1) | 2022.12.01 |
[C++] 쿼드트리 (1992번) (1) | 2022.11.27 |
[C++] 이중 우선순위 큐 (7662번) (0) | 2022.11.25 |
[C++] 최소 힙 (1927번) (0) | 2022.11.23 |