백준 5525 - ioioi [SIVLER 1]

5525_ioioi

문제

최초 입력 N이 들어오면, N+1 개의 I와 N개의 O가 교차로 나오는 문자열을 Pn이라 합니다.

즉, IOI 는 P1, IOIOI는 P2를 의미합니다.

N과 문자열 S의 길이, 그리고 문자열 S가 들어왔을 때, S안에는 Pn이 몇 개가 포함됐는지 출력합니다.

딱 봐도 S의 0부터 순회하며 문자열을 일일히 검증하는 건 무조건 시간 초과가 생길 것 같은 문제입니다.

첫 번째 시도, 50점 짜리 정답

이번 문제는 제약 사항이 두 가지 버전이 있습니다.

배점	제한
50	N ≤ 100, M ≤ 10 000.
50	추가적인 제약 조건이 없다. N ≤ 1,000,000, M ≤ 1,000,000

즉, 원래 문제의 N이 100, M이 10,000 까지 있는 문제를 해결할 수 있는 코드는 50점 짜리 정답이 됩니다.

늘 그렇듯 이번에도 50점을 맞고 시작합니다.

import sys, re

input = sys.stdin.readline

Pn = 'I'

N = int(input())
Pn += 'OI'*(N)
L = int(input())
S = input().strip()

dos = re.sub('O{2,}', '', S)
dis = re.sub('I{3,}', 'II', dos)

ans = 0
l = len(Pn)

i = 0
while i < len(dis):
    if dis[i] == 'I':
        if dis[i:i+l] == Pn:
            ans += 1
            i += 1
    i += 1

print(ans)

위의 코드에서는 정규표현식을 활용해 O가 2연속 이상인 부분을 모두 삭제하고,

I가 3번 이상인 부분을 모두 II로 바꾸었습니다.

만약 N = 2이고 S = IOIIIOIOI일 때, Pn은 1번 등장하지만,

III를 I로 치환하거나, 없앨 경우 2번 또는 0번으로 바뀌기 때문입니다.

이러한 발상은 좋았으나, (사실 정답에서는 크게 중요하지 않았기에, 오버헤드였을 뿐이었습니다.)

두 번째 시도, 대환장 리소스 파티

모든 인덱스를 훑는 다는 게 큰 문제였던 것 같습니다.

단순히 생각해서 1,000,000개의 문자열을 쭉 훑고

I가 보이면 일단 [index : index + len(Pn)]로 슬라이싱해서 매칭하다보니 빠를 수 없었습니다.

인덱스를 하나하나 증가하지 말고 쓸 데 없는 부분에선 도약할 필요가 있습니다.

인덱스에 따라 문자열을 읽던 중 정답이 보이면

정답 끝부분 인덱스(index + len(Pn))로 건너가 +2까지에 OI가 붙어있는지 확인하는 식으로 식을 수정했습니다.

import sys, re

input = sys.stdin.readline

N = int(input())
Pn = 'i'+'OI'*(N)
L = int(input())
S = input().strip()

dos = re.sub('O{2,}', '', S)
dis = re.sub('I{3,}', 'II', dos)

ans = 0
l = len(Pn)
flag = 0

i = 0
while i < len(dis):
    if flag:
        if dis[i:i+2] == 'OI':
            ans += 1
            i += 1
        else:
            flag = 0
    if not flag and dis[i] == 'I':
        # 이 부분을 주목하자
        if dis[i:i+l] == Pn:
        # 여기까지 말이다.
            i += l-1
            ans += 1
            flag = 1
    i += 1

print(ans)

간신히 정답의 범주에 들긴 했으나 이걸 풀었다고 할 수는 없을 것 같습니다.

세 번째 시도, find()와 정답 코드

어떻게든 연산횟수를 줄일 방법을 찾으려고 했는데 답은 find 메서드였습니다.

Python의 많은 기본 메서드와 함수는 내부 로직이 C로 짜여진 경우가 많습니다.
Python 코드로 굳이 그것들을 직접 구현하면 손해입니다.

왜 굳이 한 거 또 하냐고~

def find(string, target)
    i = 0
    while i < len(string):
        if string[i: i+len(target)] == target:
            return i
    else:
        return -1

위의 코드는 find()가 수행하는 연산을 python으로 짠 것입니다.

그리고 두 번째 시도의 while문 내부에는 이와 비슷한 검색 코드가 있었습니다.

즉, 그냥 그 부분만 find로 바꾸면 되는 것이었습니다!

import sys

input = sys.stdin.readline

N = int(input())
Pn = 'I' + 'OI'*(N)
L = int(input())
string = input().strip()

ans = 0
l = len(Pn)
flag = 0

i = 0
while i < len(string):
    if flag:
        if string[i:i+2] == 'OI':
            ans += 1
            i += 2
        else:
            flag = 0
    else:
        # 바뀐 부분은 사실상 여기 뿐이다.
        i = string.find(Pn, i)
        # find의 두 번째 인자는 검색을 시작할 index다.
        # i를 계속해서 find로 찾아낸 index로 도약하면 된다.
        if i == -1:
            break
        ans += 1
        i += l
        flag = 1

print(ans)

python으로 직접 구현한 find를 그저 기존의 메서드를 사용했을 뿐인데 20배 가량 빨라졌습니다.

위의 방법 이후로, 문자열 자체를 find로 찾아낸 인덱스까지 꾸준히 슬라이싱 하는 방법도 사용하여 속도를 점차 줄여나갔습니다.

그 과정에서 정규 표현식이 되려 오버헤드였다는 것을 깨닫고는 지워버렸습니다.

그런데, 비슷한 연산을 거치는 코드들이 구현체의 차이로 시간복잡도가 다르게 설정된다는 게...

사실 당연하지만 문제 풀이에서도 파이썬은 편하지만 느리다는 특성이 그대로 가는 군요.