mojo's Blog

[백준 5525] IOIOI 본문

백준/etc

[백준 5525] IOIOI

_mojo_ 2021. 6. 30. 23:23

문제 링크 => 5525번: IOIOI (acmicpc.net)

 

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이 몇

www.acmicpc.net


문자열 관련 문제이다.

 

이문제의 핵심은 시간복잡도 O(N) 으로 해결하도록 하는것이다.

 

문자열의 index = 0 부터 접근한다고 할 때, 'I' 를 발견하는 경우에 대해 살펴보도록 한다.

(이때,  'O', 'I' 가 iterate 하는 것을 판별하기 위한 변수 j 와 IOI, IOIOI, IOIOIOI, ... 를 판별하기 위한 변수 op 설정)

 

Initialization :  j 값을 0으로 초기화하고 i 값을 1증가시킨다.

 

Step 1 :  j 가 0인경우 => 이 경우에는 이전 문자가 'I' 였으므로 'O' 인 경우 j 값을 1로 변경

           이때, 'I' 인 경우 IOI...OII 와 같은 경우이므로 다시 I부터 확인해가도록 해야한다.

           따라서 op값을 0으로 변경하고 j 는 0을 유지한다. (즉, Step 1을 다시 실행하도록 함)

 

Step 2 :  j 가 1인경우 => 이 경우에는 이전 문자가 'O' 였으므로 'I' 인 경우 op 값을 1증가 및 j 값을 0으로 변경

           그리고 IOI, IOIOI, ... 이 경우를 op값으로 처리하므로 op값이 n값 이상인 경우 Counting 해준다.

           이때, 'O' 인 경우에 IOI...IOO 와 같은 경우이므로 이 경우에는 while문을 빠져나오도록 해준다.

           즉, 이 경우에는 for문을 통해 'I'를 다시 찾는 경우 Initialization 으로 다시 이동한다.

 

Step 1, 2 를 반복해가며 찾아간다면 시간복잡도 O(N) 만큼 해결할 수 있다.


풀이 Code   

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <time.h>
#define INF 100000000
#define endl '\n'

using namespace std;

void solve(int n, int m, string s) {
	int op = 0, cnt = 0;
	for (int i = 0; i < m; i++) {
		if (s[i] == 'I') {
			int j = 0;
			i++;
			while (i < m) {
				if (j == 0) {
					if (s[i] == 'O') {
						j = 1;
					}
					else {
						op = 0;
					}
				}
				else {
					if (s[i] == 'I') {
						op++;
						j = 0;
						if (op >= n) cnt++;
					}
					else {
						op = 0;
						break;
					}
				}
				i++;
			}
		}
	}
	cout << cnt;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	int n, m;
	string s;
	cin >> n >> m >> s;

	solve(n, m, s);

	return 0;
}
Comments