파이썬 알고리즘 - 문자열에 포함된 문자들이 전부 유일한지 검사

개발자 면접 트레이딩 - 파이썬 알고리즘 문제(1)

 

 

(1). 개발자 면접 트레이닝 - 문자열에 포함된 문자들이 전부 유일한지 검사하는 알고리즘

① 모든 문자를 비교하는 것은 시간 복잡도가 높으므로, 부적합하다고 볼 수 있다.

② Hash를 사용하여 시간 복잡도를 낮추는 방향으로 작성해 보도록 하자.

③ 아스키 코드는 모두 256개

④ 예를들어 ABCD 는 -> 순수 문자열 , ABAD -> 중복 문자열

(2). 소스 코드

PYTHON

# isUniqChar.py

def isUniqChar(str):

    if(len(str) > 256):
        return False

    hash = [False] * 256

    for ch in str:
        #print(ord(ch)) 문자를 아스키 코드번호로 변환
        if(hash[ord(ch)]) is True:
            return False
        else:
            hash[ord(ch)] = True
    return True

def isUniqCharResult(result):
    if(result):
        print("Duplicate Characters Not Exist.")
    else:
        print("Duplicate Characters Exist.")


if __name__ == '__main__':

    isUniqCharResult(isUniqChar("abcda"))
    isUniqCharResult(isUniqChar("abcde"))
    isUniqCharResult(isUniqChar("apple"))

 

(3). 소스 코드 분석

① 10 라인 : 아스키 번호를 담기위해 256개의 구조 생성

② 15 라인 : 아스키 코드가 저장되어 있으면, 중복된 문자 확인

③ 19 라인 : 새로운 문자이면 True를 저장

④ 22 라인 : 결과를 문자열로 출력하기 위한 함수 작성

⑤ 30 라인 : 프로그램 컴파일 및 실행

파이썬(Python) 으로 작성한 후 같은 코드를  Java 변환하여 작성해보면 더욱 도움이 될 것이다.

(4). 실행결과