[BOJ] 5525 : IOIOI [문자열](Python)

문제 링크

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

5525번: IOIOI

소스 코드

import sys
input = sys.stdin.readline

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

# 투 포인터 알고리즘
left, right = 0, 0
cnt = 0

while right < m: # m 범위 내에서 반복
    # 3개 슬라이싱한 것이 'IOI'인 경우
    if s[right:right + 3] == 'IOI':
        right += 2 # 오른쪽 두 칸 이동
        # 길이 조건을 만족하는 경우
        if right - left == 2 * n:
            # 카운트하고 오른쪽으로 두 칸 이동
            cnt += 1
            left += 2
    else: # 조건 만족하지 않는 경우
        # 오른쪽으로 한 칸 이동
        right += 1
        left = right

print(cnt)

 

해설

• 시간복잡도 고려 필수
• 투 포인터 알고리즘

시간 복잡도를 고려하지 않은 풀이를 제출하면 50점으로 채점된다.

m,n의 범위가 최대 1,000,000까지이므로 매번 리스트에 슬라이싱하여 비교하면 시간 복잡도가 너무 높아져 시간 초과하게 되는 것이다.

따라서 투 포인터 알고리즘을 이용하여 중복되는 슬라이싱을 줄일 수 있다(시간 복잡도는 슬라이싱 길이에 비례하여 증가한다).

 

변수의 의미

문자열 Pn은 문자열 IOI 가 반복되는 꼴이다.

따라서 시작점을 기준으로 우측으로 두 칸만 더 비교하면 된다. 이 기준은 right라는 변수가 된다.

 

반복은 right, 즉 문자열의 오른쪽 인덱스가 m 미만일 동안에만 진행된다.

인덱스가 m이 되는 순간 인덱스 범위를 초과하게 되는 것이다(인덱스는 0부터 시작하므로)

 

검사 과정

right라는 변수를 기준으로 세 칸을 슬라이싱하여 문자열 'IOI'인지 확인한다. 

만약 맞을 경우 이후 얼마나 반복되는지 확인하기 위하여 우측으로 두 칸 이동한다.

이동 후 현재까지의 결과가 문제에서 주어진 n번 반복되는 p와 동일한지 확인한다. 

p와 동일하다면 카운트하고 그 모양 그대로 움직여 탐색할 수 있도록 왼쪽 left도 오른쪽으로 두 칸 이동한다.

 

만약 현재까지 'IOI'가 반복된 것이 주어진 p와 일치하지 않는 경우에는 if right - left == 2*n 조건을 만족하지 못하여 right 만 우측으로 두 칸 이동한다. 

즉 시작점은 left에 남겨 두고 right만 오른쪽으로 이동하여 탐색 범위를 늘려주는 것으로 이해할 수 있다.

 

반면 right를 기준으로 세 칸 슬라이싱 한 것이 'IOI'와 다를 때는 애초에 확인할 필요가 없으므로 right와 left를 둘 다 오른쪽으로 한 칸 이동하여 탐색을 다시 수행한다.