[파이썬, Python] 백준 5525: IOIOI

문제

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

5525번: IOIOI

코드

n = int(input())
m = int(input())
s = input()

s = s[s.find("IOI"):s.rfind("IOI")+3]

start, end = 0, 0
cnt = 0

while end < m:
    if s[end:end + 3] == "IOI":
        end += 2
        if end - start == 2 * n:
            cnt += 1
            start += 2
    else:
        end += 1
        start = end
        
print(cnt)

설명

처음에는 단순 슬라이싱으로 해결하려고 하니 서브태스크 1번만 맞아서 다른 방법을 고민했다.

투 포인터로 탐색해야 할 지점을 더 줄이니 해결이 가능했다.

우선 n, m, s를 입력받는다.

추가적으로 s를 변경하는데 시작 점은 IOI가 처음으로 나오는 지점,
끝 지점은 IOI가 마지막으로 나오는 지점+3 까지다. (find의 경우 시작 지점의 인덱스를 반환한다.)

그리고 start와 end, cnt를 세팅해 주었다.

end가 m이 되기 전까지 반복을 한다.

만약 s의 부분문자열이 IOI라면 end를 2 늘려준다.
이렇게 하면 지금 찾은 IOI의 뒤쪽 I로 이동한다.

이 과정 중에 만약 end에서 start를 뺀 것이 2 * n과 같다면,
이는 우리가 찾는 Pn이므로 카운트를 해주고
start를 2 늘려주어 현재의 앞부분에서 IO를 뺀 그 이후 부분을 탐색한다.

만약 s의 부분문자열이 IOI가 아니라면,
end를 1 늘려주어 다음 문자열부터 탐색하게 하고,
그 이전의 부분은 의미가 없게 되므로 start를 end로 초기화해 준다.

최종적으로 cnt를 출력한다.