하나의 문자열이 주어졌을 때, 해당 문자열이 헤테로그램(Heterogram)인지 아닌지 판별하는 것이 이번 글의 목표입니다.
헤테로그램이란 알파벳 글자가 단 한 번도 반복되지 않는 단어, 문구, 또는 문장을 의미합니다. 즉, 문자열에 포함된 모든 문자가 서로 달라야 합니다. 참고로 헤테로그램은 알파벳의 모든 글자를 최소 한 번씩 사용하는 팬그램(Pangram)과는 다른 개념입니다.
예제
입력 문자열: abc def ghi
헤테로그램입니다. (반복되는 알파벳이 없음)
입력 문자열: abc bcd dfh
헤테로그램이 아닙니다. (b, c, d가 반복됨)
알고리즘
- 먼저 문장에 포함된 모든 알파벳을 리스트로 분리합니다.
- 알파벳 리스트를 집합(set)으로 변환합니다. 집합은 중복 값을 저장하지 않기 때문입니다.
- 집합의 길이가 알파벳 개수와 같다면 각 알파벳이 한 번씩만 등장한 것이므로 헤테로그램이며, 그렇지 않다면 헤테로그램이 아닙니다.
방법 1: 해시 배열 사용
크기가 26인 배열을 만들어 각 알파벳의 등장 여부를 기록하고, 이미 등장한 알파벳이 다시 나타나면 즉시 False를 반환하는 방식입니다.
def stringheterogram(s, n):
# 각 알파벳(a~z)의 등장 여부를 기록하는 해시 배열
hash = [0] * 26
for i in range(n):
if s[i] != ' ': # 공백은 무시
index = ord(s[i]) - ord('a')
if hash[index] == 0:
hash[index] = 1 # 처음 등장한 알파벳 표시
else:
return False # 이미 등장한 알파벳 → 헤테로그램 아님
return True
# 실행 코드
s = input("문자열 입력 ::>")
n = len(s)
result = "헤테로그램입니다" if stringheterogram(s, n) else "헤테로그램이 아닙니다"
print(f"{s} -> {result}")방법 2: 집합(set) 활용
파이썬다운 간결한 방법으로, 알파벳만 추출한 뒤 집합으로 변환하여 길이를 비교하면 됩니다.
def is_heterogram(s):
# 공백을 제외하고 알파벳만 추출
letters = [ch for ch in s if ch.isalpha()]
# 집합으로 변환했을 때 길이가 같으면 중복 없음
return len(set(letters)) == len(letters)
# 실행 코드
s = input("문자열 입력 ::>")
print(s, "->", "헤테로그램입니다" if is_heterogram(s) else "헤테로그램이 아닙니다")참고 사항
- 방법 1의 코드는 소문자 기준으로 동작하므로, 대소문자를 함께 처리하려면
s[i].lower()를 적용하면 됩니다. - 두 방법 모두 시간 복잡도는 O(n)으로 문자열 길이에 비례하여 효율적으로 동작합니다.
출력 결과
문자열 입력 ::> asd fgh jkl asd fgh jkl -> 헤테로그램입니다 문자열 입력 ::> asdf asryy asdf asryy -> 헤테로그램이 아닙니다