Algorithm/Implementation

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

안드선생 2021. 4. 26. 10:35
반응형

www.acmicpc.net/problem/5525

 

5525번: IOIOI

첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다. (1 ≤ N ≤ 1,000,000, 2N+1 ≤ M ≤ 1,000,000)

www.acmicpc.net

문제 설명

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이 몇 군데 포함되어 있는지 구하는 프로그램을 작성하시오.


풀이 과정

문자열 S를 for문을 돌면서 i를 만날 경우 현재 인덱스를 stack에 넣어준다.

(예를 들어, ooioi일 경우 스택에 2, 4가 들어있을 것이다.)

stack의 각 원소들의 차이가 2인 경우는 i가 한 칸을 띄어져있다는 뜻이므로

이런 경우에 cnt를 하나씩 늘려준다.

 

이 때, cnt가 n이상일 경우 answer을 하나씩 추가해준다.

import sys
n = int(input())
m = int(input())
s = sys.stdin.readline()

cnt = 0
answer = 0
stack=[]

for i in range(m):
    if s[i] == "O":
        continue
    else:
        stack.append(i)

for i in range(1, len(stack)):
    if stack[i] - stack[i-1] == 2:
        cnt += 1
    else:
        cnt = 0

    if cnt >= n:
        answer += 1


print(answer)

 

https://github.com/HongEunho

 

HongEunho - Overview

📖 Android, Java, Kotlin, Algorithm. HongEunho has 15 repositories available. Follow their code on GitHub.

github.com

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

반응형