[백준] 5525번 IOIOI C++

 

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

알고리즘 분류

문자열

 

---

Hint

 

해당 문제는 서브태스크가 있어

제약 조건에 따라 점수가 달라집니다

 

저는 여기서 시간 복잡도와 연관되어 있다고 생각을 했고

시간 복잡도를 만족할 수 있는 생각을 했습니다

 

그래서 시간 복잡도에 상관 없이 코드를 짠다면

직접 모든 구간을 IOI로 구성되어 있는지 확인하면 될 것이고

시간 복잡도를 고려하여 코드를 짠다면

IOI가 있는지에 대한 판단을 할 때 계산이 필요하다 생각했습니다

---

Solution

 

시간 복잡도를 고려하여

문자열을 하나하나 탐색하지 않고

문자열을 판단할 때 int형 배열을 하나 추가적으로 이용하여

반복되고 있으면 +1을 하고 반복되지 않으면 초기화 하여 계산했습니다

 

뒤에서부터 탐색하여 반복되는지 확인했고

현재 문자와 다음 문자가 다르다면 이전 수열에 +1씩 추가해서 더해줬고

(dp처럼)

 

현재 문자와 다음 문자가 같을 때는 초기화를 해주었습니다

(I일때는 1, O일때는 0으로)

I를 1로 초기화한 이유는 O는 사이에 I가 껴있어야 하지만

I는 그 이후에 O가 껴있을 수도 있기 때문에 계산을 위해 1로 초기화합니다

 

#include <iostream>

using namespace std;

int main() {
	int N, M;
	cin >> N >> M;
	int* repeat = new int[M]; // IOI가 반복되는지에 대한 계산 수열
	// I 다음 O가 나오면 +1, O 다음 I가 나오면 +1 식으로 계산
	string S;
	cin >> S;
	
	char recent = S[M - 1]; // recent는 뒤 문자와 비교할 문자(현재 진행 중인)
	if (recent == 'O') repeat[M - 1] = 0;
	else repeat[M - 1] = 1;

	for (int i = M - 2; i >= 0; i--) {
		recent = S[i];
		if (recent == S[i+1]) { // 다음 문자가 동일하면 초기화
			if (recent == 'I') { // I의 경우는 +1을 해준다
				repeat[i] = 1;
			}
			else
				repeat[i] = 0;
		}
		else { // 다음 문자가 동일하지 않은 경우
			repeat[i] = repeat[i + 1] + 1;
		}
	}

	int answer = 0;
	for (int i = 0; i < M-1; i++) {
		// 만약 N=1이라면 IOI가 중복되는 곳을 탐색하기 위해선
		// 3이상의 홀수가 몇 개 있는지 탐색하면 된다
		if (repeat[i] >= 2 * N + 1 && repeat[i] % 2 == 1) {
			answer++;
		}
	}

	cout << answer;
	
}

 

위 같이 진행하면 O(N)의 속도로 계산되는 것을 볼 수 있습니다.