[백준 5525] IOIOI [Python]

백준 1992 - 입/출력

백준 5525 - 문제

백준 5525 - 입/출력

---

풀이

입력으로 주어진 문자열 S 안에 2N + 1길이의 Pn이 겹침을 허용해서 몇 개 존재하는지 찾으면 되는 문제다.

최대 길이 M에 대한 Pn의 길이는 (100만 - 1) 이기 때문에, 아래처럼 모든 구간에서의 Pn을 구하면 시간초과가 발생한다.

N = 2, M = 15, S = IOIOIOIOIOIOIOI 일 때,
IOIOI
    IOIOI
        IOIOI
            ...
처럼 매번 2N + 1 길이만큼의 문자열이 주어진 문제의 조건을 만족시키는지 확인하면 시간초과가 발생할 것이다.
때문에, 이미 조건을 만족시키는 문자열을 다시 확인하지 않고 풀이하는 방법이 필요하다.

먼저, 올바른 Pn이 만들어지는 조건을 살펴보자

• Pn은 'I' 부터 시작한다.
• 문자열 S의 M - 1 번째가 'I' 아니면, Pn은 만들어지지 않는다.
• 이미 만족하는 Pn을 찾았고, 겹치는 Pn이 있는지 확인하기 위해서는 Pn + "OI"가 존재하는지 살펴보면 된다.

직관적으로 풀이하기 위해 조건에 맞는 Pn을(CASE) 만들어주었다. 

M - 1번째의 문자까지만 탐색하며, 문자열 S가 'I'로 시작하는지 아래와 같이 설정해주자.

위의 조건을 만족한다면, 조건을 만족하는 Pn이 만들어지는지 반복문을 통해 살펴보아야 한다.

만약 조건을 만족하지 않는다면 탐색 시점을 증가시켜주어 다음 index를 살펴보자.

 

# 문자열 S 중 올바른 Pn이 만들어지는지 살펴보는 간단한 방법.
S[idx : idx + SIZE] == CASE
'''
일치하면 탐색 시점을 SIZE만큼 더해주면 되지만,
일치하지 않을 경우 다음 탐색 차례를 특정지을 수 없어 불필요한 탐색이 발생한다.
'''

현재 살펴보고 있는 index에서 SIZE만큼 구간이 CASE와 일치한다면 올바른 Pn이 만들어질 것이다.

index overflow를 주의해 조건을 설정해주자.

만약 CASE와 일치하지 않으면 올바른 Pn이 아니기 때문에 탐색 시점(jump)을 다음에 살펴볼 index에(idx) 적용해주어, 불필요한 탐색을 방지했다.

 

만약 올바른 Pn이 만들어졌다면, 이후에는 추가로 Pn이 겹쳐서 만들어질 수 있는지 (오른쪽으로 Pn이 확장 가능한지) 확인하면서 결과값과 탐색할 시점을(idx)을 증가시켜주면 된다.

---

소스코드

소스코드 보기

---

출처

5525번: IOIOI