Q. 문자열에서 처음으로 반복되지 않는ㄴ 문자를 찾아내는 효율적인 함수를 작성하라. 예를 들어 "total"에서 처음으로 등장하는 반복되지 않는 문자는 'o'이며, "teeter"에서 처음으로 등장하는 반복되지 않는 문자는 'r'이다. 자신이 작성한 알고리즘의 효율에 대해 논하라.
A.
1) 가장 쉬운 방법은 특정 문자를 그 문자열에 있는 다른 모든 문자와 비교하여 그 문자가 반복되는지 아는 방법이다. 하지만 이같은 풀이는 실행시간이 오래걸린다. 문자열 길이가 n이라면 최악의 경우 n개의 문자들을 모두 n번씩 비교해야 한다.(마치 버블 정렬같이) 즉, 시간복잡도 O(n^2)을 가진다.
그렇다면 더 효과적으로 해결할 수 있는 방법은 없을까?
2) 이 문제는 데이터에 대한 효율적인 검색을 할 수 있는지 유도하는 문제이다. 선형검색(O(N))보다 효율적으로 검색할 수 있는 방법은 이진검색(Binary Search(O(nlogn)))과 계산검색인 해시(O(n), O(1))를 통해 가능 하다.
해시 테이블을 이용한다면 입력되는 문자열을 선형시간안에(O(N)) 탐색할 수 있다.
하지만, 배열을 이용한 선형탐색도 같은 시간 복잡도가 든다. 그렇다면 둘 중 선정해야할 기준을 공간복잡도 기준으로 볼 수 있다. 해시 테이블을 사용할 경우 입력된 문자열에 들어있는 서로 다른 문자 개수만큼을 저장할 공간만 있으면 된다.
따라서 가능한 문자의 개수가 적으면서 긴 문자열을 처리 할 때는 배열을 쓰는 편이 낫고, 문자열이 짧은 경우나 문자 개수가 많은 인코딩을 사용하는 경우에는 해시 테이블을 쓰는 것이 효율적이다.
<해시를 이용한 해결 방법 - 시나리오>
우선 문자 개수를 셀 해시 테이블을 만든다:
각 문자에 대해서
그 문자에 해당하는 값이 저장되어 있지 않으면 1을 저장
그렇지 않으면 저장된 값을 1 증가시킴
문자열을 훑어 본다:
각 문자에 대해서
해시 테이블에 저장된 값이 1이면 그 문자를 반환
저장된 값이 1인 문자가 없으면 널을 반환
<Code>
public String firstNonRepeated(String str){
String result = null;
Hashtable hashtable = new Hashtable();
Character c;
Object seenOne = new Object();
Object seenTwo = new Object();
// 입력된 str을 훑으면서 해시 테이블을 만든다.
// 한번 입력되면 seenOne 플래그를 , 두번 이상 입력된다면 seenTwo 플래그를 해당 문자에 입력한다.
for(int i = 0; i < str.length(); i++){
c = new Character(str.charAt(i));
Object temp = hashtable.get(c);
if(temp == null){ // 현재 문자가 해쉬 테이블에 없으면 테이블에 추가한다.
hashtable.put(c, seenOne); // 처음 한번이기 때문에 한번 봤다는 플러그인을 value값으로 넣는다.
}
else{ // 1번이상 이미 나왔던 문자라면
hashtable.put(c, seenTwo);
}
}
// 입력된 문자열을 기준으로 순서에 맞춰 해당 문자가 몇번 나왔는지 판단한다. 1개가 나온 문자열을 찾으면 반복문은 바로 종료한다.
for(int i = 0; i < str.length(); i++){
c = str.charAt(i);
if(hashtable.get(c) == seenOne){
result = c.toString();
break;
}
}
return result;
}
여기서 HashTable에 int,char 같은 형을 저장하지 않는 이유는, HashTable에는 Object 객체에 대한 레퍼런스가 저장 할 수 있기 때문이다.