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

서브태스크

 

예제

 

---

나의 풀이

50점짜리 풀이

n = int(input())
m = int(input())
s = input()
pn = 'IO'*n+'I'
unit = 2*n+1
answer = 0
for i in range(0, m-unit):
    if s[i:i+unit]==pn: answer += 1
print(answer)

입력 받은 n에 따라 pn을 만든다.

unit은 pn의 길이이다.

이렇게 직접 비교해서 찾는 방법은 50점을 받았다.

 

100점짜리 풀이

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

stack = [i for i in range(len(s)) if s[i]=='I']
count, answer = 0, 0

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

print(answer)

stack에 'I'의 인덱스를 저장한다.

저장된 'I'들의 인덱스가 2 간격으로 있다면 IOIOI... 의 형식을 가지는 것이다. IOOI는 간격이 3일테고, IIO는 간격이 1일 것이다.

만약 n으로 2를 입력 받았다면 IOIOI가 일치해야한다. 즉, I의 간격이 2번 연속 2씩 차이난다면 IOIOI 패턴에 일치하는 것이다.

IOIOIOI일 때 IOIOI는 2개 포함된다. 이것은 IOIOI가 발견된 이후로 2 간격으로 I가 등장할 때마다 answer을 하나씩 올려주면 된다는 것이다.

그러다가 I의 인덱스 간격이 2 차이가 아닌 1이나 3 이상 차이난다면 count에 0을 저장하고 다시 찾아야 한다.

위 50점짜리 풀이와 비교했을 때 이 풀이는 O(n)의 시간 복잡도로 풀이 가능하다.

채점 결과