[Baekjoon] 5525_IOIOI

Silver I

문제(출처: https://www.acmicpc.net/problem/5525)

---

< IOIOI >

 

문제 풀이 

 

처음에는 문자열을 전체 탐색하면서 Pn과 일치하는지를 확인했다. 이 과정에서 서브 태스크 50점을 획득했다.

 

50점 (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(bf.readLine());
		int s = Integer.parseInt(bf.readLine());
		String str = bf.readLine();

		String x = "";
		for (int i = 0; i < n; i++) {
			x += "IO";
		}
		x += "I";

		int result = 0;

		for (int i = 0; i < s - (n * 2); i++) {
			if (str.charAt(i) == 'I') {
				String temp = str.substring(i, i + (n * 2 + 1));
				if (temp.equals(x)) {
					result += 1;
				}
			}
		}
		System.out.println(result);
	}

}

 

남은 50점을 획득하기 위해 시간을 줄여야 했다.

위에서는 구하려는 문자열 길이만큼 계속해서 문자열을 잘라서 확인해서 오래 걸렸던 것이었다.

이 부분을 해결하기 위해 문자열을 한번 탐색하면서 IOI의 개수를 구하여 답을 구했다.

 

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(bf.readLine());
		int s = Integer.parseInt(bf.readLine());
		String str = bf.readLine();

		int cnt = 0;
		int i = 0;
		int result = 0;
		while (i < s - 2) {
			if (str.charAt(i) == 'I' && str.charAt(i + 1) == 'O' && str.charAt(i + 2) == 'I') {
				cnt += 1;
				i += 2;
			} else {
				if (cnt >= n) {
					result += cnt - n + 1;
				}
				cnt = 0;
				i += 1;
			}
		}
		if (cnt >= n)
			result += cnt - n + 1;

		System.out.println(result);
	}

}

 

Main

변수)
n : Pn의 n
s : str의 길이
str : 문자열
cnt : 문자열에서의 IOI 개수
i : 문자열 탐색 index
result : str에 Pn이 포함되어 있는 횟수

 

- n, s, str 입력

- 문자열을 탐색

  1) IOI라면 cnt증가 및 index +2 

  2) IOI가 아니라면 여태 IOI가 나온 횟수(cnt)가 Pn만큼 있다면 result에 값 더해줌. Pn만큼 있는지 없는지 상관없이 cnt를 0으로 초기화 후 index+1

- 문자열 탐색 후 마지막에 Pn이 나왔을 수 있으므로 확인 후 result에 값 더해주기

- result 출력

---

---