개요
이 글에서는 주어진 문제를 해결하기 위한 접근 방식과 구현 방법에 대해 자세히 알아보겠습니다.
문제 정의
문자열이 입력으로 주어졌을 때, 해당 문자열에 포함된 모든 문자가 고유한지, 즉 중복된 문자가 존재하는지 판별해야 합니다.
접근 방법
불리언(Boolean) 값으로 구성된 배열을 생성합니다. 인덱스 i에 위치한 플래그 값은 알파벳의 i번째 문자가 문자열에 포함되어 있는지 여부를 나타냅니다.
동일한 문자를 두 번째로 만나는 순간 즉시
False를 반환합니다. 이미 문자열의 문자들이 더 이상 고유하지 않음이 확인되었기 때문입니다.문자열의 길이가 알파벳의 고유 문자 수를 초과하는 경우에도
False를 반환할 수 있습니다. 비둘기집 원리에 따라 반드시 중복이 발생하기 때문입니다.
여기서는 문자열의 최대 크기를 256으로 가정합니다.
이제 실제 구현 코드를 살펴보겠습니다.
예제 코드
def isUniqueChars(st):
if len(st) > 256:
return False
# 초기화
char_set = [False] * 128
# char_set 검사
for i in range(0, len(st)):
# ASCII 값
val = ord(st[i])
if char_set[val]:
return False
char_set[val] = True
return True
# 메인 함수
st = "tutorialspoint"
print(isUniqueChars(st))
실행 결과
False
'tutorialspoint'라는 문자열에는 't'와 'i'가 각각 여러 번 등장하므로, 위 코드는 False를 출력합니다.
복잡도 분석
시간 복잡도: O(n) — 문자열을 한 번만 순회하며 각 문자를 상수 시간 안에 처리합니다.
공간 복잡도: O(1) — 크기가 고정된 불리언 배열(128 또는 256)만 사용하므로 입력 크기와 무관하게 일정한 메모리를 사용합니다.
아래 그림과 같이 모든 변수는 전역 프레임(global frame)에 선언됩니다.
결론
이 글에서는 불리언 배열과 ASCII 값을 활용하여 문자열 내 모든 문자가 고유한지 효율적으로 확인하는 방법을 학습했습니다. 이 기법은 추가적인 자료구조를 사용하지 않고도 선형 시간 안에 문제를 해결할 수 있는 대표적인 코딩 인터뷰 유형 중 하나입니다.