5525번 - IOIOI

2024-02-07

#C++#백준

문제 링크

문제 풀이 시간 : 1시간

문제 요약

•
n+1개의 I와 n개의 O로 이루어진 문자열이 있다. (IOIOI…)

•
I,O로 이루언진 문자열 S가 주어졌을 때, S안에 위의 문자열이 몇번 포함되어 있는지 구해라

문제 풀이

초기 코드

C++

#include <iostream>
#include <string>

using namespace std;

int main() {
    int n, m, sum = 0;
    string input;
    string io = "I";
    cin >> n >> m >> input;
    for (int i = 0; i < n; i++) { //io문자열 만들기
        io += "OI";
    }
    for (int i = 0; i < m; i++) { //몇번 포함 찾기
        if (input[i] == 'I') { 
            if (input.substr(i, 2 * n + 1) == io) //문자열 잘라서 io와 같은지 비교
                sum++;
        }
    }
    cout << sum;
}

위 코드는 50점을 받았다.

문자열의 최대 길이가 1,000,000이라 시간초과는 안나올거라고 생각했는데

1,000,000이 들어가면 시간초과가 나는 것 같다.

이유는 잘 모르겠지만

substr이 생각보다 많이 느린 듯하다.

그래서 다른 방법을 생각하다가 생각이 안나서 참고했다..

최종 코드

C++

#include <iostream>
#include <string>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, m, sum = 0;
    string input;
    cin >> n >> m >> input;
   
    for (int i = 0; i < m; i++) {
        int temp = 0;
        if (input[i] == 'I') { 
            while (true) {
                if (input[i + 1] != 'O' || input[i + 2] != 'I') //I를 이미 찾았으므로 뒤에 OI가 있는지 확인
                    break;
                temp++;
                if (temp == n) { //현재까지 찾은 io의 길이가 찾고자 하는 io의 길이와 같다면
                    temp--; //다음번 확인을 위해 길이 -1
                    sum++;
                }
                i += 2; //i+1, i+2를 확인 했으므로 i+2해주기
            }
        }
    }
    cout << sum;
}