[BaekJoon] 백준 5525번 : IOIOI

5525번 : IOIOI

그냥 반복문을 통해 1부터 1,000,000 까지 돌기만 해도 2.8초가 걸린다.

때문에 O(N^{^}2) 인 알고리즘으로는 절대 풀 수 없고 O(N) 도 index 를 전부 순회하면 시간 초과가 발생한다.

find 함수를 통해 풀고 싶었지만 안될 껄 알아서 손도 안대보고 규칙을 찾기 시작했다.

1. Solution1

   만약 IOIOIOIOI 가 주어지고 찾고자 하는 문자열이 IOIOI 라면 3개가 존재한다.

   IOI 패턴을 계속 찾아 내가 찾고자 하는 문자열의 패턴과 일치하면 그때 값을 올린다.

   그리고 패턴을 찾았다면 index 는 두 칸을 올리면 된다.

   IOIOIOIOI 에서 첫 번째 IOIOI 를 찾았다면 패턴은 1을 뺀다.

   그래야 다음 IOIOI 를 찾을 수 있기 때문이다.

   패턴이 끊긴다면 다시 패턴을 초기화 한 뒤 index 를 한 칸만 올려 다시 검사하며 반복한다.

   
   

2. Solution2

   사실 solution1 풀이보다 먼저 생각했던 풀이는 주어진 문자열에서 연속하지 않는 부분을 모두 찾아내 비교하는 방법이었다.

   IIIOIOIOOOI 가 주어진다면 패턴인 IOIOIO 를 찾아내 비교를 하는 것 이다.

   그런데 이 패턴을 찾아내는게 너무너무 생각보다 어려웠다..

   분명히 정규식을 사용하면 될 것 같긴 했는데 아직 정규식으로 문자열을 다루기는 부족한 실력..

   다음에 꼭 필요한 정규식 정도는 공부를 해야겠다.

   어쨌든 연속하지 않는 부분의 길이에서 찾고자 하는 문자열의 길이를 뺀 값을 2 로 나눈뒤 1 을 더해주면 답이 된다.

---

import sys
import re


def solution1(N, str_size, string):
	count = pattern = idx = 0

	while idx < str_size - 1:
		if string[idx - 1] == 'I' and string[idx] == 'O' and string[idx + 1] == 'I':
			pattern += 1
			if pattern == N:
				count += 1
				pattern -= 1
			idx += 1

		else:
			pattern = 0
		idx += 1

	return count


def solution2(part, sub_len):
	count = 0
	for val in part:
		if len(val) >= sub_len:
			count += (len(val) - sub_len) // 2 + 1

	return count


N = int(sys.stdin.readline().rsplit()[0])
str_size = int(sys.stdin.readline().rsplit()[0])
_string = sys.stdin.readline().rsplit()[0]

print(solution1(N, str_size, _string))

part = re.findall('I(?:OI)+', _string)
print(solution2(part, 1 + 2 * N))