이 글에서는 리스트 컴프리헨션(List Comprehension)과 OrderedDict를 활용하여 파이썬에서 문자열 내 K번째 비반복 문자를 찾는 방법을 알아봅니다. 별도의 외부 라이브러리 설치 없이 파이썬에 기본으로 제공되는 내장 구조만으로 문제를 손쉽게 해결할 수 있습니다.
문제 이해하기
'비반복 문자(non-repeating character)'란 문자열에서 정확히 한 번만 등장하는 문자를 의미합니다. 예를 들어 "tutorialspoint"라는 문자열에서 각 문자가 몇 번 나오는지 세어, 한 번만 등장하는 문자들 중에서 K번째에 해당하는 문자를 찾는 것이 목표입니다.
알고리즘
1. 먼저 입력 문자열로부터 딕셔너리 데이터를 생성합니다. 2. 각 문자의 등장 빈도를 계산합니다. 3. 값이 1인(한 번만 등장하는) 모든 키의 리스트를 추출합니다. 4. 마지막으로 k-1번째 인덱스의 문자를 반환합니다.
OrderedDict를 사용하는 이유
OrderedDict는 키가 삽입된 순서를 그대로 유지하는 딕셔너리입니다. 덕분에 원본 문자열에서의 등장 순서대로 비반복 문자를 추출할 수 있다는 점이 핵심입니다. 참고로 파이썬 3.7부터는 일반 dict도 삽입 순서를 유지하지만, 하위 버전과의 호환성을 고려하면 OrderedDict를 사용하는 것이 안전합니다.
예제 코드
from collections import OrderedDict
import itertools
def kthRepeating(inp, k):
# 딕셔너리 데이터 생성 (모든 값을 0으로 초기화)
dict = OrderedDict.fromkeys(inp, 0)
# 각 문자의 빈도수 계산
for ch in inp:
dict[ch] += 1
# 값이 1인 모든 키(비반복 문자)의 리스트 추출
nonRepeatDict = [key for (key, value) in dict.items() if value == 1]
# (k-1)번째 문자 반환
if len(nonRepeatDict) < k:
return 'no output.'
else:
return nonRepeatDict[k-1]
# 드라이버 함수
if __name__ == "__main__":
inp = "tutorialspoint"
k = 3
print(kthRepeating(inp, k))
실행 결과
a
코드 동작 방식 상세 설명
OrderedDict.fromkeys(inp, 0)는 문자열 "tutorialspoint"의 각 문자를 키로, 값을 0으로 초기화한 순서가 유지되는 딕셔너리를 만듭니다. 이후 반복문을 돌며 각 문자의 개수를 하나씩 더해 빈도를 계산합니다.
그다음 리스트 컴프리헨션 [key for (key, value) in dict.items() if value == 1]은 빈도가 정확히 1인 문자들만 골라 새로운 리스트를 만듭니다. "tutorialspoint"에서 한 번만 등장하는 문자들은 순서대로 'u', 'r', 'a', 'l', 's', 'p', 'n'입니다.
k=3이므로 리스트의 세 번째 요소인 'a'가 최종 결과로 출력됩니다. 또한 비반복 문자의 개수가 k보다 적을 경우 "no output." 메시지를 반환하도록 예외 처리까지 포함되어 있어 안정적으로 동작합니다.
결론
이 글에서는 리스트 컴프리헨션과 OrderedDict를 조합하여 파이썬에서 K번째 비반복 문자를 찾는 방법을 살펴보았습니다. 이 접근 방식은 시간 복잡도 O(n)으로 효율적이며, 코드 역시 간결하고 읽기 쉽습니다. 문자열 분석이나 빈도 계산 등 다양한 실무 문제에 응용할 수 있는 유용한 패턴이니 꼭 기억해 두시기 바랍니다.