[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)

 

 

구현코드