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

문제

문자열에 포함된 문자들이 전부 유일한지를 검사하는 알고리즘을 구현하라.

다른 자료구조를 사용할 수 없는 상황이라면 어떻게 하겠는가?

 

풀이

배열을 제외한 모든 다른 자료구조를 사용하지 않고 문자들이 전부 유일한지를 검사해야합니다.

 

우선 스탠다드 아스키코드를 기준으로 문자는 총 128가지가 있기 때문에

문자열의 길이가 128이 넘으면 중복이 존재하는 경우이므로 이 경우를 먼저 확인합니다.

 

이후에는 총 4가지 방법으로 검사할 수 있습니다.

 

1. 128크기의 boolean형 배열에 각 문자가 존재하는지를 표시하고 동일한 문자가 다시 접근하는지 확인

시간 복잡도 : O(n) 공간 복잡도 : O(1)

 

2. 문자가 알파벳 소문자로만 이루어졌다는 가정하에 26자리를 정수형 변수에 비트로 표시하고 동일한 문자가 다시 접근하는지 확인

시간 복잡도 : O(n) 공간 복잡도 : O(1) (1번 방법보다 1/8 줄어든다)

 

3. 문자열의 각 문자를 다른 모든 문자와 비교

시간 복잡도 : O(n²) 공간 복잡도 : O(1)

 

4. 문자열을 정렬한 후 인접한 두 문자가 동일한지를 비교

(C++ STL sort 사용 시) 시간 복잡도 : O(nlogn) 공간 복잡도 : O(n)

 

 

구현코드

 

	#include <string>
	#include <algorithm>
	using namespace std;
	//1번
	bool isUniqueChar1(string str){
	//Standard ASCII 기준 128가지의 문자가 있기 때문에
	//문자열의 길이가 128을 넘으면 중복된 문자열이 존재하게된다.
	if(str.length() > 128) return false;
	bool char_set[128];
	for(int i=0;i<str.length();i++){
	int val = str[i];
	if(char_set[val])
	return false;
	char_set[val] = true;
	}
	return true;
	}
	//2번
	bool isUniqueChar2(string str){
	if(str.length() > 26) return false;
	int checker = 0;
	for(int i=0;i<str.length();i++){
	int val = str[i] - 'a';
	//1번 방법에서 boolean형 배열에 표시하는 것처럼
	//해당 알파벳이 존재하는지를 int형 변수에 비트로 표시한다.
	if((checker & (1 << val)) > 0)
	return false;
	checker |= (1 << val);
	}
	return true;
	}
	//3번
	bool isUniqueChar3(string str){
	if(str.length() > 128) return false;
	//서로 다른 모든 문자를 비교한다.
	for(int i=0;i<str.length();i++)
	for(int j=i+1;j<str.length();j++)
	if(str[i] == str[j])
	return false;
	return true;
	}
	//4번
	bool isUniqueChar4(string str){
	if(str.length() > 128) return false;
	//문자열 정렬 후 인접한 두 문자를 비교한다.
	sort(str.begin(), str.end());
	for(int i=1;i<str.length();i++)
	if(str[i-1] == str[i])
	return false;
	return true;
	}

view raw array_and_string1.cpp hosted with ❤ by GitHub