[Baekjoon] 5525번 : IOIOI (Python, 문자열)

[Baekjoon] 5525번 : IOIOI (Python, 문자열)

 

목차

 

 

 

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

5525번: IOIOI

 

코드 링크

https://github.com/stellaluminary/Baekjoon

GitHub - stellaluminary/Baekjoon

 

Python

 

50점(시간 초과) - 방법 1 - 메모리 30840KB / 시간 76ms / 코드 길이 152B

 

 s의 길이-2만큼 모두 살피는 경우 여기서는 시간이 오래 걸린다고 판단한다.

 

 

n = int(input())
m = int(input())
s = input()
p = 'IO'*n + 'I'
cnt = 0

for i in range(m-len(p)+1):
    if s[i:i+len(p)] == p:
        cnt += 1
print(cnt)

 

방법 2 - 메모리 32796KB / 시간 284ms / 코드 길이 260B

 

방법 1에서는 s의 길이-2만큼 모두 살폈지만 여기서는 IOI의 개수에 따른 i의 값에 따라 while문을 진행한다. (하나씩 증가하는 것이 아님)

 

가령 예를들어 n=2인 경우 P = 'IOIOI'이다.

처음 'IOI'를 발견하면 i는 i+2만큼 증가하므로 'I'에서부터 시작하여 다시 'IOI'가 발견되는지 재탐색한다.

만약 발견된다면 i에 따른 IOI 개수를 기준으로 cnt를 추가할 수 있다.

cnt는 IOI의 개수를 의미한다.

 

여기서 IOI의 개수 cnt가 n이라는 것은 우리가 원하는 P를 찾았다는 것이다.

이때 ans의 값을 하나 올린다.

 

만약 발견되지 않는다면 다음 index 값으로 넘어가서 찾는다.

 

때로는 2칸씩 때로는 1칸씩 움직이며 이에 대한 결과를 진행하는 것이 1칸씩 진행하는 것보다 빨라 시간 초과가 일어나지 않는다고 판단한다.

 

n = int(input())
m = int(input())
s = input()
ans, i, cnt = 0, 0, 0

while i <= (m-2):
    if s[i:i+3] == 'IOI':
        i += 2
        cnt += 1
        if cnt == n:
            ans += 1
            cnt -= 1
    else:
        i += 1
        cnt = 0

print(ans)