[C++] 문자열 치환하기

0. Intro

백준 마라톤 브론즈 문제를 풀며 c++ 기본 문법을 익히고 있다

적용했던 내용을 잊지 않기 위해 작성한다

 

1. 문제

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

 

백준의 브론즈 1 문자열 압축 해제 문제이다

문자열 변환에서 기본적인 내용으로 구성되어 있다

 

처음엔 `abbb`가 주어지고, `ab`는 `a`로 치환 가능한 경우처럼 중복 치환의 경우를 고민해야 하나 생각했다

그러나 브론즈 1 문제답게 변환된 문자는 대문자 알파벳 한 자리이고, 변환 전 문자는 소문자로 구성된 단어였다

그리고 변환된 대문자 알파벳을 통해 원래 문자를 복구하고, 마지막 주어진 인덱스만 출력하면 되는 문제였다

 

2. 풀이

2-1. 처음 풀이

pair를 통해 java의 Hashmap처럼 사용해 소문자와 대문자를 저장하였다

그리고 입력을 다 받은뒤에, `pair`를 저장한 `vector`를 순회하며 `after`로 정의한 문자열에 해당 대문자가 있는지 찾았다

`vector`의 사이즈만 돌기 때문에 속도가 더 빠를 것이라 생각했는데, 이게 웬걸 오히려 속도가 느렸다

 

`find`와 `replace` 함수를 사용한 반복문에서 시간이 더 걸렸을 것이라 예상해 본다

 

int main() {
	int N;
	cin >> N; // N 입력

	vector<pair<string, string>> keyword;

	for (int i = 0; i < N; i++) {
		string s1, s2;
		cin >> s1 >> s2;
		keyword.push_back(make_pair(s1, s2));
	}

	string after;
	cin >> after;

	int startIdx, endIdx;
	cin >> startIdx >> endIdx;

	// 모든 입력 종료, after 문자를 기반으로 replace 진행
	// 키워드를 기반으로 루프 진행
	for (int i = 0; i < keyword.size(); i++) {
		string from = keyword[i].first; // from
		string to = keyword[i].second; // to

	//	to를 다시 from으로 변경
		while (after.find(to) != -1) {
			after.replace(after.find(to), to.length(), from);
		}
	}

	cout << after.substr(startIdx-1, endIdx - startIdx + 1);

	return 0;
}

 

`after.find(to)` 함수를 사용해서 있으면 반복문을 돌리고, 없으면 `-1`을 반환해 종료하게 만들었다

그리고 해당 루프문 내에서는 찾은 문자열(`after.find(to)`)의 시작부터 종료(`to.length()`)까지를 from으로 대체했다

`replace`함수를 사용할 때 문자열이 길어질수록 속도가 느려지지 않을까?

c++ `replace` 함수의 시간 복잡도는 `O(N + M)`이다, 원본 문자열의 길이(N) + 치환될 문자열의 길이(M)으로

여기서는 1000 + 1일 것이다

 

그러나 다른 방식은 조금 더 빠르다

문자열을 뒤에 추가만 해주는 방식이라 `O(N)`의 시간 복잡도를 가진다

 

하지만 여기서 이 `replace`의 의미는 크게 없어 보인다, 최대가 1,000이고 M 또한 1이니까

 

그렇다면 `find`가 조금 더 오래 걸리는 원인이 아닐까?

 

`find`는 최악 시간 복잡도가 일반적으로 `O(N * M)`이다

원본 문자열의 길이(N)과 치환될 문자열의 길이(M)으로 나타낼 수 있다

이 부분이 확실히 오래 걸린다

 

치환될 문자열의 길이는 대문자 → 소문자이기 때문에 소문자 패턴의 최대 길이 1,000이다

또한 압축된 문자열의 길이는 최대 1,000 이걸 하나씩 치환해 나가면 최악의 경우

1,000자의 대문자가 주어지고, 패턴 또한 모든 대문자가 1,000자를 가지는 경우이다

 

따라서 시간 복잡도가 O(N * M)이므로 1,000,000(백 만)번의 연산이 진행된다

그래서 이 부분을 고쳐 시간 효율성을 높였다

 

 

2-2. 효율 개선 코드

int main() {
	int N;
	cin >> N; // N 입력

	vector<pair<string, char>> keyword;

	for (int i = 0; i < N; i++) {
		string s1;
		char s2;
		cin >> s1 >> s2;
		keyword.push_back(make_pair(s1, s2));
	}

	string after, before;
	cin >> after;

	int startIdx, endIdx;
	cin >> startIdx >> endIdx;

	// 모든 입력 종료, after 문자를 기반으로 replace 진행
	// 키워드를 기반으로 루프 진행
	for (int i = 0; i < after.size(); i++) {
		for (int j = 0; j < keyword.size(); j++) {
			if (after[i] == keyword[j].second) {
				before += keyword[j].first;
				break;
			}
		}
	}
	cout << before.substr(startIdx - 1, endIdx - startIdx + 1);

	return 0;
}

 

입력 출력은 동일하지만, 루프문 내용을 바꾸었다

또한 대문자를 `char` 형태로 받아 사용하였다

 

1. 변환된 문자열을 탐색하며, 해당 문자열의 대문자가 어떤 소문자로 치환되는지 확인하기 위해 `vector`를 순회한다

2. 찾았다면, 이전 문자열에 해당 소문자를 붙여넣고 루프를 종료한다

3. 다음 변환된 문자로 진행한다

 

3. 마무리

`replace`와 `find`를 사용한 것보다는 문자열 변환시 탐색 범위가 점점 길어지는 부분이 시간 효율을 떨어뜨린 것 같다

시간 복잡도를 고려하며 문제를 풀고, 효율을 개선하는 노력을 계속 진행해야 겠다