[백준/BOJ] silver1 - 5525번 IOIOI (Python)

▶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이 몇 군데 포함되어 있는지 출력한다.

 

▶서브태스크

번호	배점	제한
1	50	N ≤ 100, M ≤ 10 000.
2	50	추가적인 제약 조건이 없다.

728x90

▶풀이

처음에는 n에 해당하는 string을 찾아서 기록한 다음, 하나씩 비교해 보았다.

통과는 되었지만 서브태스크 2를 통과하지 못해서 50점만 받았다.

 

<50점 받은 코드>

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

IOI = 'IO' * n + 'I'
answer = 0

for i in range(0, m - n - 1, 1):
    tmp = s[i : i + len(IOI)]
    if IOI == tmp:
        answer += 1

print(answer)

 

새로 생각한 방법이 'IOI'개씩만 비교하는 방법이다.

하나씩 다 비교하는 것이 아닌 +2씩 넘어가기에 시간 복잡도 측면에서 더 나을 것이라고 생각했다.

그리고 IOI카운트만 해주고 n이랑 비교해 주면 된다고 판단했다.

그렇게 문제를 풀고 제출하니까 정답이 나왔다.

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

answer, i, count = 0, 0, 0

while i < m - 1:
    if s[i : i + 3] == 'IOI':
        i += 2
        count += 1
        if count == n:
            answer += 1
            count -= 1
    else:
        i += 1
        count = 0

print(answer)