백준 5525번 IOIOI

문제 링크입니다: https://www.acmicpc.net/problem/5525

직관적으로 O(N^2)으로 풀면 TLE가 발생하는 문제입니다.

따라서, 시간 복잡도를 O(N)으로 줄여야합니다.

핵심은 O의 개수를 통해 Pn인지를 파악하는 것이였습니다.

물론, OO와 같이 예외가 발생할 수 있으므로 조건문을 통해 OI가 연속으로 등장하는지 파악합니다.

검사할 때 첫 번째로 등장한 O는 이후에는 안 쓰이므로 다음 Pn을 검사할 때는 해당 O는 제외함으로써 시간 복잡도 O(N)으로 문제를 풀 수 있습니다.

#include <iostream>

#include <string>

using namespace std;

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int N, len;

        string s;

        cin >> N >> len >> s;

 

        int result = 0;

        //O(N)으로 풀어야한다

        for (int i = 0; i < s.length(); i++)

        {

                 if (s[i + 1] == 'O' && s[i + 2] == 'I')

                 {

                         //O의 개수가 중요

                         int O = 0;

                         while (s[i] == 'I' && s[i + 1] == 'O')

                         {

                                 i += 2;

                                 O++;

                                 if (s[i] == 'I' && O == N)

                                 {

                                          O--; //이전 O는 확인 안해도 된다

                                          result++;

                                 }

                         }

                 }

        }

        cout << result << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~