코딩 인터뷰 완전 분석 1.1 파이썬3 풀이

문제

1.1 중복이 없는가: 문자열이 주어졌을 때, 이 문자열에 같은 문자가 중복되어 등장하는지 확인하는 알고리즘을 작성하라. 자료구조를 추가로 사용하지 않고 풀 수 있는 알고리즘 또한 고민하라.

 

제한 사항

1. 문자열의 길이 제한 없음.
2. 문자열의 중복 여부만 판단하면 됨.
3. 문자열이 정렬되어 있는지 아닌지는 없음.
4. 문자의 구성이 알파벳이라는 제한도 없음.
5. 자료구조를 추가로 사용해서 안 됨. (추가사항)
6. 대소문자 구분에 대한 이야기도 없음.

 

아이디어1

문자를 키값으로 해쉬테이블에 한 문자 씩 넣는다.

각 해쉬테이블의 값의 크기를 조사한다.

크기가 2 이상이 발견되면 True, 발견되지 않으면 False

공간복잡도

O(n)

시간복잡도

O(n)

 

아이디어2

(자료구조 사용 X)

문자열을 정렬한다. -> O(nlogn)

자신과 뒤의 문자를 비교하면서 같으면 True, 발견되지 않으면 False -> O(n)

공간복잡도

O(1)

시간복잡도

O(nlogn)

 

아이디어3

만약에 문자가 알파벳이라는 제한이 있다면,

52개의 알파벳과 문자열을 비교하여 수를 세면 된다. -> O(52n)에 가능

공간복잡도

O(1)

시간복잡도

O(n)

 

테스트케이스

True 경우

• 11
• 1,2av[fd]ba
• b1,2av[fd]b
• 1,2,3,4,5,6,7,8,9

 

False 경우

• 1,2av[fd]b
• 1
• 12
• abcdefghijklmnop
• 2140avd

 

코드

아이디어 1

def is_duplicated(input_string):
    char_table = {}

    for char in input_string:
        char_table[char] = 0

    for char in input_string:
        char_table[char] += 1

        if char_table[char] > 1:
            return True

    return False


# True 경우
print(is_duplicated('11'))
print(is_duplicated('1,2av[fd]ba'))
print(is_duplicated('b1,2av[fd]b'))
print(is_duplicated('1,2,3,4,5,6,7,8,9'))

# False 경우
print(is_duplicated('1,2av[fd]b'))
print(is_duplicated('1'))
print(is_duplicated('12'))
print(is_duplicated('abcdefghijklmnop'))
print(is_duplicated('2140avd'))

아이디어 2

def is_duplicated(input_string):
    sorted_string = sorted(input_string)

    for index in range(1, len(sorted_string)):
        if sorted_string[index] == sorted_string[index-1]:
            return True
    return False


# True 경우
print(is_duplicated('11'))
print(is_duplicated('1,2av[fd]ba'))
print(is_duplicated('b1,2av[fd]b'))
print(is_duplicated('1,2,3,4,5,6,7,8,9'))

# False 경우
print(is_duplicated('1,2av[fd]b'))
print(is_duplicated('1'))
print(is_duplicated('12'))
print(is_duplicated('abcdefghijklmnop'))
print(is_duplicated('2140avd'))

아이디어 3은 위의 2개 케이스가 모두 잘 커버해 줄 수 있으므로 넘어감.

힌트

#44 해시테이블을 사용해보라

#117 비트 벡터가 유용한가?

#132 O(NlogN) 시간에 풀 수 있겠는가? 그 해법은 어떤 것인가?

해답

책에서는 아이디어 3의 방법을 사용해서 구현하였다. 알파벳 한정이 아닌, 아스키코드 한정으로 해서 128 크기의 Boolean 배열을 만들었다.

비트 벡터를 사용해서 공간을 1/8로 줄여서도 구현했는데 비트 벡터에 대해 한번 살펴볼 필요가 있겠다.