[알고리즘] 백준 5525 IOIOI (파이썬 풀이)

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

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

 

해결코드

import sys
input = sys.stdin.readline

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

ans = 0
cnt = 0
i = 1

while i < M - 1:
    if S[i-1] == "I" and S[i] == "O" and S[i+1] == "I":
        cnt += 1
        if cnt == N:
            cnt -= 1
            ans += 1
        i += 1
    else:
        cnt = 0
    i += 1

print(ans)

문제풀이

• P1 IOI
• P2 IOIOI
• P3 IOIOIOI

위의 예를 보면 P(n)에서 n은 IOI가 나오는 개수이다.

그래서 문제를 해결할 때 IOI가 나오는지 확인하고 맞다면 count 값을 올린다.

카운트 값이 입력받은 N과 일치한다면 answer값을 올리는 방법이다.

 

코드를 보자

 

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

차례대로 N,M,S를 입력받아준다.

ans = 0
cnt = 0
i = 1

결과를 출력할 ans, IOI의 개수를 셀 cnt, while문에서 쓰일 i값을 설정해준다.

while i < M - 1:
    if S[i-1] == "I" and S[i] == "O" and S[i+1] == "I":
        cnt += 1

while문을 실행시킨다(i=1부터 i=M-1 까지의 범위)

만약 연속하는 3개의 문자가 IOI라면

cnt값을 1 더해준다.

        if cnt == N:
            cnt -= 1
            ans += 1
        i += 1

그리고 만약 cnt값이 N과 같아졌다면,

cnt값을 1빼주고 ans값을 1 더해준다.

i값에 1을 더해준다(더하는 이유: OI가 반복되기 때문에 두 칸을 띄어줘야 한다)

    else:
        cnt = 0
    i += 1

연속된 문자가 IOI가 아니라면 cnt값을 0으로 초기화한다.

if문을 탈출해서 i에 1을 더한다

print(ans)

ans값을 출력해준다.