[백준] 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이 몇 군데 포함되어 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다.

출력

S에 PN이 몇 군데 포함되어 있는지 출력한다.

제한

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

서브태스크

번호 배점 제한
1 50
N ≤ 100, M ≤ 10 000.

2 50
추가적인 제약 조건이 없다.

예제 입력

1
13
OOIOIOIOIIOII

예제 출력

4

풀이

풀이1: 단순 계산 -> 시간 초과

시간 복잡도: O(N*M), (파이썬의 슬라이싱(복사) 길이 M)

주어진 배열을 앞에서부터 차례로 순회하면서 현재 인덱스를 pn 의 마지막 인덱스라 가정하고, pn과 일치하는지 확인한다.

n = int(input())
m = int(input())
arr = list(input())
cnt = 0
pn = []
for i in range(n):
    pn.append("IO")
pn.append("I")
pn = "".join(pn)

for i in range(len(pn)-1, m):
    if "".join(arr[i-len(pn)+1:i+1]) == pn: cnt+=1
print(cnt)

풀이2: 시간 줄이기1 -> 시간 초과

시간 복잡도: O(N*M), (파이썬의 슬라이싱(복사) 길이 M)

풀이1과 유사하게주어진 배열을 앞에서부터 순회하면서 pn 과 일치하는지 확인하는데,

직전이 성공 기록인 경우(인덱스 +=2 된 경우)

• 현재 위치에서 직전칸과 합이 'O','I'인 경우 -> 결과+=1,idx+=2
• 현재 위치에서 직전칸과 합이 'O','I'가 아닌 경우 -> idx+=1, 실패 기록

직전이 실패 기록인 경우(인덱스+=1 된 경우)

• 현재 위치에서 pn과 일치하는 경우 -> 결과+=1,idx+=2, 성공 기록
• 현재 위치에서 pn과 일치하지 않는 경우 -> idx+=1

이렇게 하면 현재 위치에서 성공일때는 인덱스를 증가(+2)시킴으로서 연산을 줄이고, 직전이 성공인 경우 현재 위치에서 pn 전체를 확인하는게 아니라, 길이 2만큼만 확인하면 되서 시간 복잡도를 줄일 수 있다. 여전히 시간 초과 발생

주의) 직전 성공 시 파이썬의 슬라이싱 길이가 2라서 전체 시간복잡도를 O(2*N)이라 착각할 수 있다. 그러나 대부분의 경우는 슬라이싱의 길이가 M일 것이다!

import sys
input = sys.stdin.readline
n = int(input())
m = int(input())
arr = list(input())
cnt = 0
pn = []
for i in range(n):
    pn.append("IO")
pn.append("I")
pn = "".join(pn)

idx = len(pn)-1 # 만약 len(pn)이 5면 idx 4부터 시작함
isCorrect = False
while idx < len(arr):
    if isCorrect == False: # 직전 케이스가 올바르지 않았던 경우
        if "".join(arr[idx-len(pn)+1:idx+1]) == pn: # 현재 케이스에서 다시 검사
            cnt+=1 # 올바른 경우
            idx+=2 # 2칸뒤로 이동(1칸뒤는 볼 필요 없음)
            isCorrect = True
        else: # 현재 케이스에서도 올바르지 않은 경우
            idx+=1 # 1칸 뒤로 이동
    else: # 직전 케이스가 올바른 경우
        if "".join(arr[idx-1:idx+1]) == "OI": # 현재도 올바른 경우
            cnt+=1
            idx+=2 # 2칸뒤로 이동(1칸뒤는 볼 필요 없음)
        else: 
            isCorrect = False # 현재는 올바르지 않은 경우
            idx+=1
    
print(cnt)

풀이3: 시간 줄이기2 -> 성공

시간복잡도: O(3*M), (파이썬의 슬라이싱(복사) 길이 3)

pn과 일치하는지 한번에 비교하는게 아니라, ioi 패턴이 반복적으로 나타나는 횟수를 세어 비교한다.

예를 들어, ioi가 1이고, ioioioi는 3이다. 따라서 pn과 비교하는게 아니라, n과 비교하는 방식이다. => 성공

import sys
input = sys.stdin.readline
n = int(input())
m = int(input())
arr = input()

idx = 2 # idx 기준으로 앞에 부분 판별함
count,result =0,0
while idx < len(arr):
    if arr[idx-2: idx+1] == "IOI":
        count+=1
        if count == n:
            result+=1
            count-=1
        idx+=2
    else:
        idx+=1
        count=0
print(result)

시간 복잡도 관련

아무리 중간 중간을 건너뛸 수 있는 케이스를 찾았다고 해도, 테스트 케이스가 무수히 많은 경우에는 절대 시간 복잡도를 현저하게 줄일 수 없다.

예를 들어 풀이2 처럼 O(N*M)에서 이리저리 건너뛸 수 있게 처리해도 결국 풀이 1과 시간복잡도가 크지 않을것이란 뜻이다.

따라서 앞으로는 조금씩 연산을 건너뛸 수 있는 방법(예를 들어 풀이1 -> 풀이2)을 찾기보다는, 아예 다른 방법으로, 시간 복잡도를 줄일 수 있는 방법(예를 들어 풀이 3)을 고민해보자.