IOIOI

문제

백준 5525번 - IOIOI

언어

JavaScript

순서도

주어진 문자열 S 를 처음부터 끝까지 순회하며,
문자가 I 라면, 그 이후로 OI, OIOI, OIOIOI… 형태의 부분 문자열을 찾아서 Pn 이 얼마나 포함되어 있는지 구하기
Pn 의 총 포함 횟수 출력

문제 풀이 step 1

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 이 몇 군데 포함되어 있는지 구하는 문제입니다.

문제 풀이 step 2

주어진 문자열 S 를 한 글자씩 처음부터 끝까지 순회합니다.
한 글자가 O 인 경우, 그냥 무시합니다.
한 글자가 I 인 경우, 그 뒤로 ‘OI’, ‘OIOI’, ‘OIOIOI…’ 형태의 문자열을 찾아서 Pn 이 몇 번 포함되는지 구합니다.
- 만약, I 뒤에 OI 가 3 개 있다면, ‘IOIOIOI’ 가 될 것입니다.
- 이 경우 N 이 1 이라면, Pn = ‘IOI’ 이고, ‘IOIOIOI’ 안에 ‘IOI’ 는 총 3 번 등장합니다.
- 이를 식으로 풀면, 부분 문자열의 I 의 개수에 Pn 의 I 의 개수를 빼고 1 을 더해주면 됩니다.
- 위 경우,
  - 부분 문자열의 I 의 개수는 4,
  - Pn 의 I 의 개수는 2,
  - 따라서, 4 - 2 + 1 = 3 이 나오게 됩니다.
이런식으로, ‘IOIOIOIOI…’ 형태의 부분 문자열을 구하고, 그 안에 Pn 이 몇 번 포함되는지 세어주면 됩니다.
마지막으로 총 문자열에서 Pn 이 몇 번 포함되는지 출력하면 정답입니다.
추가 설명은 주석으로 작성하겠습니다.

후기

부분 문자열을 찾는 로직에서 문자열 S 를 순회하는 인덱스 i 를 갱신하는 로직을 어디에 두느냐에 따라서 알고리즘의 소요 시간이 크게 차이났습니다.
부분 문자열을 찾아갈 때마다 인덱스 i 를 갱신하는 것이 오히려 불필요한 탐색을 줄여주기에 더 빠르다는 것을 알 수 있엇습니다.
원래는 IOIOI 형태를 깨는 문자를 만날 때 인덱스 i 를 갱신했는데, 알고리즘의 소요 시간이 좀 크게 나와서 당황했습니다.

소스 코드

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

const solution = (input) => {
	const n = Number(input[0]);
	const m = Number(input[1]);
	const s = input[2];

	let res = 0;

	// 문자열 S 를 처음부터 끝까지 순회하며
	let I = 0;
	for (let i = 0; i < m; i++) {
		// 한 글자가 'O' 라면 무시
		if (s[i] === "O") continue;

		// 한 글자가 'I' 라면, 거기서부터 부분 문자열 찾기
		I += 1;
		for (let j = i + 1; j < m; j += 2) {
			if (s[j] === "O" && s[j + 1] === "I") {
				// I 의 개수를 세어주면서, 동시에 문자열 S 를 순회하는 인덱스 i 를 갱신
				I += 1;
				i = j + 1;
			} else {
				// IOIOI 형태를 깨는 문자를 만나면 반복문 종료
				break;
			}
		}

		// 부분 문자열에서 Pn 의 등장 횟수 구하기
		if (I >= n + 1) res += I - (n + 1) + 1;
		I = 0;
	}

	return res;
};

console.log(solution(input));