[JAVA] 백준 (실버1) 5525번 IOIOI

링크

https://www.acmicpc.net/problem/5525

---

문제 설명

정답률 29.719%

N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 $P_N$이라고 한다.

• $P_1$ IOI
• $P_2$ IOIOI
• $P_3$ IOIOIOI
• $P_N$ IOIOI...OI (O가 N개)

I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 $P_N$이 몇 군데 포함되어 있는지 구하는 프로그램을 작성하시오.

---

입력

첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다.

---

출력

S에 $P_N$이 몇 군데 포함되어 있는지 출력한다.

---

풀이

문자열 S에 $P_N$이 몇번 반복되는지 구하는 문제이다. 문제 자체는 간단하기 때문에 시간 복잡도를 신경써야 한다.

문자열 S의 인덱스에 대해 반복하면서 substring() 메서드로 일일이 $P_N$인지 비교한다면 문자열 S의 길이인 M과 $P_N$의 길이인 2N + 1의 곱 만큼 반복해야 하므로 시간 복잡도는 $O(M*(2N+1))$이 되고 N과 M의 최댓값은 100만이므로 시간 초과가 발생한다.

따라서 반복을 진행하면서 문자열(String)을 비교하는게 아니라 연속된 문자(Char)가 IOI 패턴이 나타날 경우 카운트하고 N만큼 카운트될 경우 정답으로 카운트한다. 이때 인덱스는 1이 아니라 2를 증가시켜 다시 I부터 카운트할 수 있도록 한다. 이때는 M만큼 반복하므로 시간 복잡도는 $O(M)$가 된다.

for (int i = 0; i < M - 2; i++) {
    if (S.charAt(i) == 'I' && S.charAt(i + 1) == 'O' && S.charAt(i + 2) == 'I') {
        patternCount++;
        if (patternCount == N) {
            answer++;
            patternCount--;
        }
        i++;
    } else {
        patternCount = 0;
    }
    
}

전체 코드

//백준
public class Main {

    public static void main(String[] args) throws IOException {

        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());
        String S = br.readLine();
        int patternCount = 0, answer = 0;

        for (int i = 0; i < M - 2; i++) {
			//연속된 문자가 IOI일 경우
            if (S.charAt(i) == 'I' && S.charAt(i + 1) == 'O' && S.charAt(i + 2) == 'I') {
                patternCount++;
                //Pn일 경우 정답으로 카운트
                if (patternCount == N) {
                    answer++;
                    patternCount--;
                }
                //i를 한 번 더 증가 시켜야 다음 I부터 비교
                i++;
            } else {
                patternCount = 0;
            }

        }

        System.out.println(answer);
    }
}