문제:
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가 주어진다. (1<=N<=1,000,000 , 2N+1 <= M <= 1,000,000)
출력:
S에 Pn이 몇 군데 포함되어 있는지 출력한다.
풀이방법:
Pn은 I와 O가 교대로 나오는 문자열이다. 따라서 index로 비교해서 IOI 패턴을 만족하는지 확인하고 이렇게 연속된 횟수를 세고 N과 일치할 경우 answer를 1 증가시킨다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
N = int(input())
M = int(input())
S = input()
answer = 0
pattern = 0
i = 1
while i < M-1:
if S[i-1]=='I' and S[i]=='O' and S[i+1]=='I':
pattern +=1
if pattern == N:
pattern -=1
answer +=1
i+=1
else:
pattern = 0
i+=1
print(answer)
|
cs |
문제링크:
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
www.acmicpc.net
'Algorithm > Python' 카테고리의 다른 글
| [Programmers]2020 카카오 인턴십. 키패드 누르기 (0) | 2020.07.07 |
|---|---|
| [BOJ]1543. 문서 검색 (0) | 2020.07.02 |
| [BOJ]11652. 카드 (0) | 2020.06.25 |
| [BOJ]5052. 전화번호 목록 (0) | 2020.06.23 |
| [BOJ]12865. 평범한 배낭 (0) | 2020.06.18 |