1.1 중복이 없는가

문제

문자열이 주어졌을때 이 문자열에 같은 문자가 중복되어 등장하는지 확인하는 알고리즘을 작성하라. 

자료구조를 추가로 사용하지 않고 풀 수 있는 알고리즘 또한 고민하라.

 

해결방법

 

1. Hash를 이용하여 해결하기 

def solution(word):
    alpha_dict = {}
    for w in word:
        if alpha_dict.get(w, 0) >0 :
            return False
        alpha_dict[w] = 1
    return True

hash라는 자료구조를 이용하여 해결하면 

Time Complexity = O(N)

Space Complexity = O(N) 

 

2. 비트벡터를 이용해 해결하기 

def solution(word):
    alcheck = 0
    for w in word:
        if alcheck & (1 << ord(w)- ord('a')) :
            return False
        alcheck |= (1 << ord(w)- ord('a'))
    return True

비트벡터를 이용하여 해결하면 

Time Complexity = O(N)

Space Complexity =O(1) 

 

3. 퀵소트를 이용해 해결하기

추가 메모리 없이 NlogN만에 해결 할 방법으로는 퀵소트를 이용할 수 있을 것 같다.

def solution(word):
    return quickSort(word)

def swap(word, i, j):
    word[i] = ord(word[i]) ^ ord(word[j])
    word[j] = chr(word[i] ^ ord(word[j]))
    word[i] = chr(word[i] ^ ord(word[j]))

def quickSort(word):
    if len(word)<2:
        return True
    pivot = word[0]
    j = 0
    for i in range(1, len(word)):
        if word[i] == pivot :
            return False
        elif word[i] < pivot :
            j += 1
            if j != i :
                swap(word, i, j)

    swap(word, 0, j)

    return quickSort(word[:j]) and quickSort(word[j+1:])

Sort를 하면서 같은 부분을 찾아내는 방식을 사용해야겠다는 생각이 들었는데, merge sort는 merge를 하는 과정에서 추가 메모리가 필요할 것으로 생각이 들었고 Quick Sort에서는 swap하는 부분에서 추가 메모리가 사용될 것 같아 우려했는데 , XOR 연산을 이용하면 추가 메모리 없이 swap이 가능하여 이 방식으로 해결 할 수 있을 것 같다.

 

놓친부분

1. 문자열이 ASCII문자열인지 유니코드 문자열인지 확인해야한다. 

2. 문자열의 길이가 문자 집합보다 큰 경우에는 바로 false를 return하도록 하기.