[백준] 5525 - IOIOI (C언어)

백준 5525 - 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에 $P_N$이 몇 군데 포함되어 있는지 출력한다.

제한

• $1 ≤ N ≤ 1,000,000$
• $2N+1 ≤ M ≤ 1,000,000$
• S는 I와 O로만 이루어져 있다.

서브태스크

번호	배점	제한
1	50	N ≤ 100, M ≤ 10 000.
2	50	추가적인 제약 조건이 없다.

 

---

 

풀이

 

시도 1

모든 문자열에 대해서 I가 나올 때마다, 뒷문자열을 확인하여 $P_n$ 이 등장하는지 확인해주었다.

만약, n = 2 라면 IOIOI가 등장하는지만 확인하면 된다.

bool find = true;
int answer = 0;
for (int i = 0; i < m; i++) {
    find = true;
    if(str[i] == 'I'){
        for (int k = 1; k < 2*n+1; k+=2) {
            if(!(str[i+k] == 'O' && str[i+k+1]=='I')){
                find = false;
                break;
            }
        }
        if(find) answer++;
    }
}

서브태스크 1에서는 최대 100 * 10000회 반복이므로 통과가 되지만, 서브태스크 2에서는 최대 1,000,000*1,000,000 반복이 되어 주어진 시간 내에 성공하지 못한다.

즉, 통과하려면 시간복잡도를 효율적으로 바꾸어야 한다.

 

시도 2

int answer = 0;
for (int i = 0; i < m; i++) {
    if(str[i] == 'I'){
        int p = 0;
        for (int k = 1; ; k+=2) {
            if(!(str[i+k]=='O' && str[i+k+1]=='I')){
                i += k-1;
                break;
            }
            p++;
        }
        if(p >= n)
        // 조건 없으면 p-n+1이 음수가 되어버리는 경우가 발생함.
            answer += p-n+1;
    }
}

반복 횟수를 줄이기 위해서, I가 등장하면 $P_n$가 만족할 때까지 검사한후, 찾아낸 P 문자열 안에 $P_n$이 몇 개 있는지 확인했다.

$P_N$ 안의 $P_k$는 $N-k+1$ 개가 존재한다. (N <= K)

이렇게 하면, $O(M)$ 정도의 시간복잡도로 답을 구해낼 수 있다.

 

전체 코드

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    char *str = (char*)malloc(sizeof(char)*m);
    scanf("%s", str);

    int cnt = 0;
    int answer = 0;
    for (int i = 0; i < m; i++) {
        cnt++;
        if(str[i] == 'I'){
            int p = 0;
            for (int k = 1; ; k+=2) {
                cnt++;
                if(!(str[i+k]=='O' && str[i+k+1]=='I')){
                    i += k-1;
                    break;
                }
                p++;
            }
            if(p >= n) // 조건 없으면 p-n+1이 음수가 되어버리는 경우가 발생함.
                answer += p-n+1;
        }
    }

    printf("%d", cnt);

    free(str);
    return 0;
}