[c++] 코딩인터뷰 완전분석 - 배열과 문자열 5

문제

같은 문자가 연속으로 반복될 경우, 그 횟수를 사용해 문자열을 압축하는 메서드를 구현하라. 가령 압축해야 할 문자열이 aabccccccccaaa라면 a2b1c8a3과 같이 압축되어야 한다. 압축 결과로 만들어지는 문자열이 원래 문자열보다 짧아지지 않는 경우, 이 메서드는 원래 문자열을 그대로 반환해야 한다.

 

풀이

문자열의 앞에서부터 같은 문자의 개수를 세고 다른 문자가 나오면 문자와 문자의 개수를 압축형태로 만들어나가면 됩니다.

 

이때 자바에서는 문자열을 + 연산으로 합치는 경우 새로운 문자열 객체를 생성하고 붙이는 작업을 수행할 때 O(n²)이 소요되어 문자배열을 사용해야 시간복잡도 O(n)으로 줄일 수 있습니다.

c++에서는 + 연산에서 새로운 문자열 객체를 생성하지 않는다고 하고 명확하진 않지만 일반적으로는 선형시간의 시간복잡도를 가진다고 하니 + 연산 혹은 append를 사용해도 무방할 것 같습니다.

 

 

구현 코드

 

	#include <string>
	using namespace std;
	//1번 : string 사용
	string compressBetter1(string str){
	string mystr;
	char last = str[0];
	int count = 1;
	for(int i=1;i<str.length();i++){
	//반복되는 문자만큼 카운트 증가시킨다.
	if(str[i] == last)
	count++;
	//반복이 끝났으면 해당 문자를 압축형태로 추가해준다.
	else{
	mystr.append(last + to_string(count));
	last = str[i];
	count = 1;
	}
	}
	//위 반복문에서 마지막 문자에 대해서는 처리되지 않았기 때문에
	//마지막 문자를 압축형태로 추가해준다.
	mystr.append(last + to_string(count));
	if(mystr.length() >= str.length())
	return str;
	else
	return mystr;
	}
	//2번 : char 배열 사용
	int setChar(char array[], char c, int index, int count){
	array[index++] = c;
	for(char x : to_string(count))
	array[index++] = x;
	return index;
	}
	string compressBetter2(string str){
	char *array = new char[str.length()];
	char last = str[0];
	int count = 1, index = 0;
	for(int i=1;i<str.length();i++){
	if(str[i] == last)
	count++;
	else{
	index = setChar(array, last, index, count);
	last = str[i];
	count = 1;
	}
	}
	index = setChar(array, last, index, count);
	if(string(array).length() >= str.length())
	return str;
	else
	return string(array);
	}

view raw array_and_string5.cpp hosted with ❤ by GitHub