IOIOI

solved_ac[Class3][IOIOI](https://www.acmicpc.net/problem/5525)

문제

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

제한

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

서브태스크

예제 입력 1

1
13
OOIOIOIOIIOII

예제 출력 1

4

예제 입력 2

2
13
OOIOIOIOIIOII

예제 출력 2

2

문제 해석

예를 들어 OOIOIOIOIIOII 라는 문자열을 입력을 받았고 N = 1을 입력을 받았다면 일단 N = 1인 문자열이 무엇인지 생각해야한다.

• N = 1 : P1 = "IOI"
• N = 2 : P2 = "IOIOI"
• N = 3 : P3 = "IOIOIOI"

이런 규칙이 나오게 되는데 여기서 생각하야 할 것은 N = 1일 때 IOI가 한 번 나오고 N = 2일 때 IOI가 두 번 나오는 것이다. IOIOI에서 왜 IOI가 두 번일까?
IOI가 한번 나오고 나서 다시 I에서 시작해서 IOI를 새는 것이다. 이렇게 생각하고 나서 풀이를 생각하면 쉽게 풀 수 있다.

풀이

첫 번째 풀이

[50점]

예시)N = 1, 2N + 1 = 13, S = "OOIOIOIOIIOII"

• 슬라이싱 이용
• Pn에 맞는 문자열 넣어주기 Pn += "I" or += "O"
• IOI를 S에서 발견하면 index를 2만큼 증가 후 다시 슬라이싱을 이용해서 Pn의 나머지 부분과 compare_str을 비교
• 다 비교해서 Pn이 compare_str안에서 발견이 되면 count를 + 1 해줌
• 만약 비교해서 아니면 어차피 index를 기준으로 슬라이싱 하기 때문에 순차적으로 다른 Pn을 찾을 수 있음.

여기서 50점이 뜬 이유는 슬라이싱 때문이다. 슬라이싱의 시간 복잡도는 list[a:b}이면 O(b-a)의 시간 복잡도가 나오게 된다.

이 슬라이싱을 이중으로 사용하기 때문에 이중 for문과 다를게 없어서 범위가 많아지게 되면 시간초과가 뜨는 것이다.

코드

import sys

N = int(sys.stdin.readline())
length = int(sys.stdin.readline())
compare_str = sys.stdin.readline()

Pn = ""

for i in range(2 * N + 1):
    if i % 2 == 0:
        Pn += "I"
    else:
        Pn += "O"
index = 0
count = 0

while True:
    if compare_str[index:index+3] == "IOI":
        index += 2
        if N == 1:
            count += 1
        else:
            a = index +  len(Pn) - 2
            if compare_str[index+1:a] == Pn[3:]:
                count += 1
    else:
        index += 1
    if index == (length - 2):
        break
    
print(count)

두 번째 풀이

[맞는 풀이]

위의 풀이에서는 슬라이싱을 이중으로 사용하기 때문에 시간 초과로 인해 점수가 50점 밖에 받지 못하였다. 그래서 IOI를 찾는 슬라이싱과 나머지 Pn을 찾는 슬라이싱까지 없애고 다르게 코딩을 하였다.

• IOI를 찾을 때, 슬라이싱이 아닌 index를 기준으로 index - 1, index, index + 1로 IOI를 찾았다.
• IOI를 찾으면 index는 2를 증가시켜주면서 다음 IOI를 찾기 위한 준비를 한다.
• IOI를 찾을 때마다 count 값을 1씩 증가시켜 준다. 맨 위에 문제 해석에서 말한 것 처럼 IOI의 갯수를 찾는 것이다.
• O를 기준 index로 삼아서 검사를 하기 때문에 index를 2 증가 시켜주면 다음 문자열 3개가 IOI라는 가정하에 compare_str[index + 2]는 "O"가 될 것이다.
• 입력에서 N값을 입력 받았는데 N값은 IOI의 개수라고 생각하면 편하다. 그래서 IOI가 연속으로 나올때마다 count를 1개씩 증가시켜주고 만약 count가 N값과 같으면 result를 +1 해준 후 count를 하나 깎아준다.
• 여기서 count를 -1 해주는 이유는 계속해서 연속되는 IOI가 나올수도 있기 때문이다. ex)N=2 일때, compare_str = "IOIOIOI" 인 경우이다.
• count - 1 연산 덕분에 계속해서 연속되어서 나오는 IOI를 계산해 줄 수 있다.
• 만약 IOI의 연속이 끊기게 되면 count를 초기화 시켜주고 index를 1만 증가 시켜준다. 바로 다음 index에서 IOI가 나올 수도 있기 때문이다.

코드

import sys

N = int(sys.stdin.readline())
length = int(sys.stdin.readline())
compare_str = sys.stdin.readline()


index = 1
count = 0
result = 0

while True:
    if compare_str[index - 1] == "I" and compare_str[index] == "O" and compare_str[index + 1] == "I":
        index += 2
        count += 1
        if count == N:
            count -= 1
            result += 1
    else:
        index += 1
        count = 0
    if index >= (length - 1):
        break
    
print(result)