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

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

5525번: IOIOI

오랜만에 부분점수가 있는 문제 

---

아이디어

1. 가장 먼저 떠오른 건 슬라이싱

• 단순하게 생각해서 그냥 Pn 크기만큼 잘라서 탐색했다.
• 아이디어가 너무 쉬운만큼 부분점수 50점만 줬다.

2. 시간 초과를 피하려면

• 이번에 알게 됐는데, 파이썬에서 arr [a:b]의 시간 복잡도는 O(b - a)라고 한다.
• 슬라이스를 최대한 덜 쓰고 반복을 최소화하는 방법을 찾아야 한다.

---

코드 설명

while cursor < (M - 1):
    if S[cursor:cursor + 3] == 'IOI': #3칸
        count += 1
        cursor += 2
        if count == N:
            result += 1
            count -= 1
    else:
        cursor += 1
        count = 0

좀 복잡해 보이지만 말로 풀어보면 간단하다.

위치를 나타내는  cursor, OI 개수를 나타내는 count 변수를 사용했다.

 

먼저 cursor부터 cousor + 3까지 3칸짜리 문자열 'IOI'가 맞는지 확인한다.

IOI가 아니라면 coursor를 한 칸 뛰고, count를 초기화해준다.

IOI가 맞다면 cursor를 두 칸 뛰고, count + 1을 해준다.

그리고 N과 비교해서 count값과 똑같다면 결괏값에 +1 해준다.

이후 count - 1을 해준다,

왜냐하면 예를 들어 IOIOIOI 문자열에서 N = 2 라면

IOIOIOI를 찾은 이후 IOIOIOI를 찾아야 하므로 count값을 1 줄여주는 것이다.

 

cursor가 문자열 끝까지 가면 while문을 종료해주면 된다.

---

전체 코드

N = int(input())
M = int(input())
S = input()

cursor, count, result = 0, 0, 0

while cursor < (M - 1):
    if S[cursor:cursor + 3] == 'IOI': #3칸
        count += 1
        cursor += 2
        if count == N:
            result += 1
            count -= 1
    else:
        cursor += 1
        count = 0

print(result)

아이디어