[백준 5525] IOIOI with Python

문제 링크

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

5525번: IOIOI

풀이

N = int(input())
M = int(input())
S = input()
P = 'IO' * N + 'I'
switch = False
count = 1
output = 0

for i in range(M):
    if not switch and S[i] == 'I': switch = True
    elif switch and S[i] != S[i-1]: count += 1
    else:
        if count >= len(P):
            output += (count - len(P))//2 + 1
        count = 1
        if S[i] == 'O': switch = False

if count >= len(P):
    output += (count - len(P))//2 + 1

print(output)

맨 처음에 무작정 아래와 같이 풀다가 시간 초과가 났다.

for i in range(M):
    if S[i:i+len(P)] == P: output += 1

모든 i에 대해서 슬라이싱을 하는 것이 시간초과의 원인이었다.

그래서 방법을 아래와 같이 바꾸었다.

S를 순회하면서 IOIOIO...구간이 나올 때 마다 그 길이를 갱신하여 그 안에 들어 있는 PN의 개수를 그때그때 output에 저장하였다.

 

S를 순회하면서

1. switch가 False인 상태에서 I가 등장하면 switch를 True로 바꾼다.

2. switch가 True인 상태에서 이전 인덱스의 원소와 다른 값이 등장하면 count를 증가시킨다.

(이전 인덱스가 I면 현재는 O이고, 이전 인덱스가 O면 현재는 I라는 의미)

3. switch가 True인 상태에서 이전 인덱스의 원소와 동일한 값이 등장하면

 - 이전 인덱스 원소까지의 IOIOIO... 구간에 속한 P_N의 개수를 output에 더한다.

 - count를 1로 초기화한다.

 - 만약 현재 원소가 O라면 switch를 False로 바꾼다.

 (만약 현재 원소가 I라면 현재 원소부터 다시 IOIOIO...구간 시작이므로 switch를 그대로 True로 둔다)

 

마지막으로 switch가 True인 상태에서 IOIOIO...구간이 끝까지 진행되어 output에 P_N의 개수를 더하는 과정이 실행되지 않을 수 있다.

그래서 마지막에 output을 더해주는 코드를 한 번 더 실행한다.