[Baekjoon] 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로만 이루어져 있다.

서브태스크

번호	배점	제한
1	50	N ≤ 100, M ≤ 10 000.
2	50	추가적인 제약 조건이 없다.

예제 입력 1

1
13
OOIOIOIOIIOII

예제 출력 1

4

• OOIOIOIOIIOII
• OOIOIOIOIIOII
• OOIOIOIOIIOII
• OOIOIOIOIIOII

예제 입력 2

2
13
OOIOIOIOIIOII

예제 출력 2

2

• OOIOIOIOIIOII
• OOIOIOIOIIOII

출처

Olympiad > Japanese Olympiad in Informatics > JOI 2013 P4번

Olympiad > Japanese Olympiad in Informatics > JOI 2009 1번

Olympiad > Japanese Olympiad in Informatics > JOI 2014 P4번

• 문제를 번역한 사람: baekjoon
• 문제의 오타를 찾은 사람: hist0613

알고리즘 분류

• 문자열

문제 풀이

# Implementation # String

풀이 과정

50점과 100점이 나눠져 있는 문제입니다.

자세한 문제 풀이는 아래에서 설명하겠습니다.

전체 코드

😂 1번 풀이: 50점

당연하게도, 처음에는 보자마자 아래와 같은 풀이를 떠올렸습니다. 하지만 결과는 50점…

아래의 풀이 같은 경우 시간 복잡도가 O(N*M)이므로 N이 커지면 시간초과를 벗어날 수 없습니다.

N, M, S = int(input()), int(input()), input()
PN = 'IO'*N+'I'
cnt = 0
for i in range(M-(2*N+1)):
    cnt += (PN == S[i:i+2*N+1])
print(cnt)

😊 2번 풀이: 100점

아래와 같은 풀이가 100점 풀이입니다. 위에서 O(N*M)이었던 시간 복잡도를 O(M)으로 줄였습니다. 각 위치마다 문자열이 IOI인지만 확인하면 됩니다.

cnt는 PN의 개수, pattern은 IOI가 연속으로 나타난 횟수입니다. 현재 위치의 문자열이 IOI이면 2개 뒤의 인덱스로 가서 검사하고, 아니면 1개 뒤의 인덱스로 가서 검사합니다.

N, M, S = int(input()), int(input()), input()
cnt, pattern = 0, 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
            cnt += 1   
        i += 1
    else:
        pattern = 0
    i += 1
print(cnt)

정리

• 패턴이 있는 문자열의 개수를 찾을 때는 패턴을 기준으로 count한다.