🐨5525]IOIOI🐍(feat번뜩이는 아이디어가 안 좋았던 건에 대하여)

https://www.acmicpc.net/problem/5525

나름대로 이런 아이디어를 떠올리고 좋아했는데....

#패턴과 부분 문자열을 뒤쪽부터 비교해서 연속 몇 개가 맞거나 틀렸는지 살펴봅니다.
def compare(a, b, len_pattern):
    count = 0
    same = a[-1] == b[-1]

    for i in range(1, len_pattern+1):
        if (a[-i] == b[-i]) == same:
            count += 1
        else:
            #same이 1이면, 홀수면 그대로 짝수면 1 빼기,
            #same이 0이면, 홀수면 1 빼고 짝수면 그대로
            count -=int(same)-(count % 2)
            return (int(same), len_pattern-count)
    return (int(same), len_pattern) #다 맞으면 2칸 전진



def find(pattern, target, len_pattern, len_target):
    fits = 0
    i = 0

    while i <= len_target - len_pattern:

        part = target[i:i + len_pattern]
        end_type, combo = compare(part, pattern, len_pattern)
        if (end_type, combo) == (1, len_pattern):#뒷 첫 글자부터 다 맞은 경우
            fits += 1
            i += 2  # 패턴을 찾은 경우, 두 칸 전진
        else:
            i += combo  # 패턴을 찾지 못한 경우, 리턴된 값만큼 전진

    return fits

n, m, target = map(str.rstrip,open(0).readlines())
n, m = map(int,(n,m))
pattern = "I"+"OI"*n

print(find(pattern, target, 2 * n + 1, m))

이 코드는 50점 밖에 받지 못했다. 문자열 슬라이싱이 생각보다 많은 시간을 잃게 된다.
python 의 슬라이싱은 할 때마다 새 객체를 만들어내는 O(n) 연산이라고 한다.
그래서 리스트 객체로 바꾸어 보기도 하고 deque로 leftpop()시켜 보기도 했지만 여전히 50점이었다.

결국 다른 사람의 코드를 참고하는데....

https://aia1235.tistory.com/30

[백준] 5525 IOIOI (python 파이썬)

아름다운 코드였다..... ㅠㅠ 다 맞으면 그 이후의 두 칸만 확인하는게 포인트

https://www.acmicpc.net/problem/5525