1 분 소요

5525번: IOIO

문제

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 ≤ N ≤ 1,000,000
  • 2N+1 ≤ M ≤ 1,000,000
  • S는 I와 O로만 이루어져 있다.


첫 번째 시도 .

n = int(input())
s_len = int(input())
s = list(input())
count=0
i=0
ans=[]
while i < s_len-2:
  if s[i]== "I" and s[i+1] =="O" and s[i+2] == "I":
    i+=2
    count+=1
  else:
    if count != 0:
      ans.append(count)
      count=0
    i+=1
if count != 0:
  ans.append(count)

result=0
for i in ans:
  if i - n + 1 > 0:
    result += i - n + 1
print(result)

»intput

2
13
OOIOIOIOIIOII

»output

2

success

image-20220301204610540


🌝 Thinking

[아이디어]

  1. OOIOIOIOIIOII 와 같은 경우 이 배열 안에 IOIOI (n=2) 가 몇 개인지 찾기위해서는

    ‘IOI’ 가 연속해서 몇 번 나타난지 카운트하면 된다. ex) ‘IOIOIOI’ 는 3이 되는 것!

  2. ‘IOI’ 가 연속해서 나오다 끊기면 카운트 값을 리스트 ans에 담고 count=0 으로 초기화해서 다시 센다.

    (즉, 연속된 ‘IOI’가 몇번 나오는지를 기록, OOIOIOIOIIOII 는 ans=[3,1]로 처리를 하겠다.)

  3. IOIOIOI 에서는 IOIOI 가 2번 나타난다. 이는 count - n + 1 = 2 라는 사실을 알 수 있다.



💡 깨달은 점.

  1. 문자열처리에서 s[i]== “I” and s[i+1] ==”O” and s[i+2] == “I” 이부분을 s[i:i+3] = ‘IOI’ 로 표현 할 수도 있다.

    (개선 사항이 있을까? 고민을 해보니!)

댓글남기기

참고