[알고리즘] 문자열의 문자 유일성 검사[알고리즘] 문자열의 문자 유일성 검사

Posted at 2015.02.11 18:29 | Posted in 알고리즘 문제



facebook에 글올리기



[알고리즘] 문자열의 문자 유일성 검사


문제. 

문자열에 포함된 문자들이 전부 유일한지를 검사하는 알고리즘ㅇ르 구현하라. 다른 자료구조를 사용할 수 없는 상황이라면 어떻게 하겠는가?


풀이


문자열은 ASCII 코드라고 가정할 때, 문자의 종류는 256자이다.

따라서 문자열의 문자들이 유일하다면, 256자가 넘을 수 없다.


boolean 형으로 256개의 배열을 정의하고, 문자열을 탐색하며, 각 문자의 ASCII 코드에 해당하는 숫자를 index로 배열에 True 값을 셋팅한다.

만약 문자열 탐색 중에 해당 ASCII 코드 인덱스가 배열에서 이미 TRUE 로 셋팅되어 있다면,


문자열에서 문자들은 유일하지 않다고 판단할 수 있다.


Colored By Color Scripter

public static boolean isUnique(String str){
        if(str.length() > 256) return false;
        
        boolean[] char_set = new boolean[256];
        
        for(int i=0; i<str.length(); i++){
            int val = str.charAt(i);
            if(char_set[val]){
                return false;
            }
            char_set[val] = true;
        }
        return true;
    }


시간 복잡도 : O(n)

간 복잡도 : O(1)



풀이 2.


다른 방법으로 비트연산을 사용하면 더 공간 사용을 1/8로 줄일 수 있다.


32비트 기준으로 비트로 32 가지를 1,0 으로 표현할 수 있으므로, 32개 이내의 문자 종류 범위 내에서는 Unique를 판단할 수 있다.

문자열의 문자를 소문자 기준으로 판단할 때, 소문자는 ASCII 코드로 97('a') ~ 122('z') 까지로 26개의 문자를 가진다.

따라서, a~z 까지를 비트의 첫번째 자리에서 26번째 자리까지의 값으로 탐색 결과를 표현할 수 있다.


문자열을 탐색하면서 문자에서 'a'를 빼면, a로 부터 몇번째 문자인지 구할 수 있으며,  "1<<val" 와 같은 비트 쉬프트로 1을 해당 번째만큼을 자리수로 표현할 수 있다.

ex> 'c' 는 'a'보다 2크다.  1<< 3  = 100


checker 변수는 checker|=(1<<val) 를 사용해, 등장한 문자에 해당하는 자리수의 값들을 1로 기록한다.

checker와 1<<val  를 & 연산했을 때, 0보다 큰 결과가 나오는 것은 1로 중복되는 자리가 있다는 것이고 이것은 유일하지 않은 결과로 판단할 수 있다.  


Colored By Color Scripter

public static boolean isUniqueChars(String str){
        if(str.length()>26) return false;

        int checker = 0;
        for(int i =0; i<str.length(); i++){
    
            int val = str.charAt(i)- 'a';
            if((checker & (1<<val))>0){
                return false;
            }
            checker |=(1<<val);
        }
        return true;
    }




이웃추가
facebook에 글올리기

Name __

Password __

Link (Your Website)

Comment

SECRET | 비밀글로 남기기