[백준(baekjoon) 5525] IOIOI

문제

백준 5525

N+1개의 I와 N개의 O가 교대로 이루어진 문자열 PN = IOIOI...OI (O가 N개)가 있다.

• 예시 : P1 = IOI, P3 = IOIOIOI
I, O로만 이루어진 문자열 S와 N이 주어질 때, S안에 PN이 몇개 들어있는지 구하시오.

해결

알고리즘

정해진 패턴을 찾는 문자열 매칭 알고리즘이라고 할 수있다.
PN은 IOI가 N개 만큼 반복되는 형태이기 때문에, KMP와 같은 별도의 알고리즘을 사용하지 않고
for문을 사용해 일일이 IOI패턴을 찾아 횟수를 센 후 N과 비교하는 방식으로 진행하였다.

• 시간 복잡도 : O(N)

설명

앞서 말한 것처럼 PN은 IOI가 N개 만큼 반복되는 형태이다.
즉, 각 index를 비교해 IOI 패턴을 만족하는지 확인하고 연속된 횟수를 센 후, N과 일치할 경우 결과 값을 1늘려주면 된다.
여기서 패턴을 만족할 경우 행해야 할 행동들이 있다.

1. 패턴 연속 횟수를 1줄여야 한다.
   why? IOI가 연속된 긴 패턴의 경우 PN이 연속으로 나타나기 때문에
2. 2칸 뒤로 이동해 패턴이 연속 되는지 확인한다.
   why? 나의 경우 자신이 O이고 앞, 뒤가 I일 때 패턴을 만족한다는 조건이므로

구현

1.import java.util.*;
2.
3.public class Main {
4.    public static void main(String[] args) {
5.        Scanner sc = new Scanner(System.in);
6.        int n = Integer.parseInt(sc.nextLine());
7.        int m = Integer.parseInt(sc.nextLine());
8.        char[] s = sc.nextLine().toCharArray();
9.
10.        int result = 0; // 최종 값
11.        int patternCnt = 0; // `IOI` 패턴 연속 횟수
12.        for (int i = 1; i < m - 1; i++) {
13.            if (s[i - 1] == 'I' && s[i] == 'O' && s[i + 1] == 'I') {
14.                patternCnt++;
15.                if (patternCnt == n) {
16.                    patternCnt--;
17.                    result++;
18.                }
19.                i++;
20.            } else patternCnt = 0;
21.        }
22.        System.out.println(result);
23.    }
24.}

결과