[백준] 5525번 - IOIOI

📩 출처

문제

N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다.

• P1 IOI
• P2 IOIOI
• P3 IOIOIOI
• PN IOIOI...OI (O가 N개)

I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 군데 포함되어 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다.

출력

S에 PN이 몇 군데 포함되어 있는지 출력한다.

👉 생각

• 일단 인덱스를 통해 구현한 절반짜리 정답 코드
• 이중 for문을 돌려서 일일히 체크해주었지만, 시간초과가 발생하는 코드였던 것 같다.

n = int(input())
m = int(input())
s = input()
# pn의 길이는 2n+1
cnt = 0
for i in range(m -(2*n+1)+1):
    check = True
    if s[i] == 'I':
        if not i % 2:
            for j in range(i, i+2*n+1):
                if (not j % 2 and s[j] == 'I') or (j % 2 and s[j] =='O'):
                    pass
                else:
                    check = False
                    break
            if check:
                cnt += 1
        else:
            for j in range(i, i+2*n+1):
                if (not j % 2 and s[j] == 'O') or (j % 2 and s[j] =='I'):
                    pass
                else:
                    check = False
                    break
            if check:
                cnt += 1
print(cnt)

• 위의 코드는 각 인덱스마다 2n+1만큼을 일일히 확인해야 했지만, 그러지 않는 방법을 써야 통과할 수 있다.
• IOI를 찾고 IOI가 몇 번 연속되는 지 개수를 체크하는 방식이다!

정답 코드

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

cnt = 0
check = 0
i = 0
while i < m-2:
    if s[i] == 'I' and s[i+1] == 'O' and s[i+2] == 'I':
        check += 1
        i += 1
        if check == n:
            check -= 1
            cnt += 1
    else:
        check = 0
    i += 1

print(cnt)