[자료구조]배열과 문자열 (1.1~1.3)

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

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

먼저 ASCII문자열인지 유니코드 문자열인지 알아야한다.

간단하게 ASCII문자열이라고 가정하고 문제 풀이 시작.

최적화 방안은 문자열의 길이가 문자 집합크기보다 클 경우 바로 false를 반환하는 것이다.

가능한 문자가 256가지밖에 없는데 주어진 문자열의 길이가 280이면, 중복이 존재한다는 거니까.

-이하 java 

방법1. 

Boolean값을 갖는 배열을 만든다. 

*Boolean: 참, 거짓 자체로 저장이 가능한 데이터.

charAt: 문자열에서 지정된 위치에 존재하는 문자를 찾아 반환하는 함수.

ex) "문자열".charAt(문자위치)

public boolean inUnique(String str){
    if(str.length()>256) return false; //주어진 문자열의 길이가 256보다 크면 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;
}

문자열의 길이가 n일때 이 코드의 시간 복잡도는 O(n), 공간복잡도는 O(1).

방법2.

문자열이 소문자a부터 z까지만 있다고 가정->하나의 int변수로 충분해진다.

public boolean inUnique(String str){
    if(str.length()>256) return false; //주어진 문자열의 길이가 256보다 크면 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;
}

방법3.

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

입력으로 주어진 문자열을 수정해도 된다면 문자열을 정렬한 다음, 문자열을 처음부터 훑어 

인접한 문자가 동일한 문자인지 검사한다. 주의, 많은 정렬 알고리즘이 추가공간을 요구한다는 점.

1.2 널 문자로 끝나는 문자열을 뒤집는 reverse(char* str)함수를 C나 C++로 구현하라.

단, 해당 배열만 사용해야 한다.

void reverse(char *str){
    char* end = str; //주어진 문자열의 끝을 저장할 포인터 end
    char tmp;
    if(str){
        while(*end){ //문자열의 끝을 찾는다.
            ++end; }
        --end; //마지막 문자열의 끝은 null이니까 한칸 앞으로.
    
    while(str<end){
        tmp = *str; //tmp에 맨 앞의 문자를 저장하고 
        *str++ = *end;//맨앞의 문자를 맨뒤와 바꾸고 포인터를 이동시킨다.
        *end-- = tmp;
        } //두 포인터가 중간지점에서 만날때까지.
    }
}

문자열의 끝을 찾고 맨 앞의 문자를 저장한다.

맨 앞의 문자를 맨 뒤의 문자와 바꾸고 포인터를 이동시킨다.(*str)

맨 뒤의 문자를 맨 앞의 문자와 바꾸고 포인터를 이동시킨다.(*end)

두 포인터가 가운데서 만날때까지 반복한다.

1.3 문자열 두 개를 입력으로 받아 그 중 하나가 다른 하나의 순열인지 판별하는 메서드를 작성하라.

대소문자 구별을 따져야하는지, 공백은 어떻게 처리하는지 주의.

일단 대소문자 구별하고 공백도 문자하나로 취급하는걸로 가정한다.

ex) "god  " 은 "dog"와 다름.

문자열 두개를 비교할때 길이가 다르면 둘은 같을 수가 없다.

apple 이랑 appl 이런식으로.

방법1. 정렬

두 문자열이 순서만 다르다면 정렬했을때, 각각을 정렬했을때 똑같은 결과가 나와야한다.

apple/alepp =>정렬시 똑같이 aelpp 이다.

public String sort(String s){
    char[] content = s.toCharArray();
    java.util.Arrays.sort(content);
    return new String(content);    
}
 
public boolean permutation(String s, String t){
    if(s.length() != t.length()){
        return false;
    }
    return sort(s).equals(sort(t));
}
 

방법2. 문자의 출현횟수가 같은지?

두 문자열이 글저 순서만 바뀐거라면, 각각의 문자 개수가 같을 것이다.

apple/alpep 두개를 봤을때 똑같이 a 1개, e 1개, l 1개, p 2개 이런것처럼.