반복되지 않는 첫 번째 문자찾기

문자열에서 처음으로 반복되지 않는 문자를 찾아내는 알고리즘을 포스팅 해보고자 합니다.

 

"akanea" 에서 반복되지 않는 문자는 무엇일까요?

 

k, n, e 입니다.

 

여기서, 처음으로 반복되지 않은 문자는 k 입니다.

 

우선, 알고리즘을 구현하기 위해 생각해 볼 사항이 있습니다.

 

'어떻게 문자를 찾을까?'

 

여기서 우리가 생각해보면 아주 간단합니다.

 

'해당 문자마다 중복되면 하나씩 카운팅해서 가장 첫번째 있는 문자 카운팅이 1 인 경우'

 

즉, akanea 가 있을때 각 문자별로 카운팅을 한다고 가정해봅시다.

 

a 는 3, k 는 1, n 은 1, e 는 1

 

여기서 첫번째 중복되지 않는 문자 k 는 카운팅이 1이므로 정답은 k 가 됩니다.

 

이 알고리즘을 실제 적용해보도록 하겠습니다.

 

우선, 어떤 문자가 반복되는지에 대해 알아내기 위해 자료구조를 통해 문자별로 검색 해볼 필요성이 있습니다.

 

우리가 사용할 자료구조는 해시맵 입니다.

 

해시맵은 평균 O(1) 의 시간 보잡도를 가지며 최악의 경우 O(n) 이라는 빠른 속도를 자랑 합니다.

 

타 자료구조에 비해 추가, 삭제, 검색 접근성이 모두 뛰어납니다.

 

이제 이 해시맵을 기반으로 이 알고리즘을 구현해보도록 하겠습니다.

 

 

알고리즘 정리

 문자 횟수를 저장할 해시 맵을 만든다.

 각 문자에 대해 해당하는 값이 저장되지 않았다면 1 저장

 그렇지 않다면 저장된 값을 1 증가 (즉, 중복 되는 문자는 1씩 카운팅 하여 증가)

 

 문자열을 처음부터 검색하여 해시맵에 문자를 찾았는데 카운팅이 1인 경우 해당 문자를 반환

 저장된 문자의 카운팅이 1이 없는 경우 NULL 처리

 

 

소스코드

public static Character firstNonRepeated(String str) {
        
    HashMap<Character, Integer> charHash = new HashMap<Character, Integer>();
    Character c;
        
    for(int i=0;i<str.length();i++) {
        c = str.charAt(i);
            
        if (charHash.containsKey(c)) { //키 존재유무
            charHash.put(c, charHash.get(c) + 1);
        }
        else { //키가 없는경우
            charHash.put(c, 1);
        }
    }
        
    //해시맵에 해당 키에 대한 문자의 갯수가 1인 경우 탐색
    for(int i=0;i<str.length();i++) {
        c = str.charAt(i);
        //순서대로 진행되다가 값이 1인 경우
        if (charHash.get(c) == 1) {
            return c;
        }
    }
    
    return null;        
}