파이썬으로 문자열에서 첫 번째 비반복 문자 찾기: 두 가지 구현 방법

문자열이나 문자 스트림에서 첫 번째로 반복되지 않는(유일한) 문자를 찾는 것은 코딩 인터뷰에서 자주 등장하는 대표적인 문제입니다. 이 문제는 다양한 방식으로 해결할 수 있으며, 이 글에서는 동일한 문자열을 대상으로 서로 다른 두 가지 파이썬 프로그램을 소개합니다.

방법 1: 함수를 사용한 구현

딕셔너리와 리스트를 활용해 각 문자의 등장 횟수와 처음 등장한 순서를 함께 기록하는 방식입니다.

def firstNonRepeatingChar(str1):
    char_order = []
    counts = {}
    for c in str1:
        if c in counts:
            counts[c] += 1
        else:
            counts[c] = 1
            char_order.append(c)
    for c in char_order:
        if counts[c] == 1:
            return c
    return None

print(firstNonRepeatingChar('PythonforallPythonMustforall'))
print(firstNonRepeatingChar('tutorialspointfordeveloper'))
print(firstNonRepeatingChar('AABBCC'))

실행 결과

M
u
None

위 프로그램은 O(n)의 시간 복잡도를 가집니다. 먼저 문자열을 한 번 순회하면서 새로운 문자를 만나면 counts 딕셔너리에 값 1로 저장하고 char_order 리스트에 추가합니다. 이미 등장했던 문자를 만나면 counts의 값을 1씩 증가시킵니다. 이후 char_order를 등장 순서대로 탐색하며 counts 값이 1인 첫 번째 문자를 찾아 반환하고, 끝까지 찾지 못하면 None을 반환합니다.

방법 2: while 루프를 사용한 구현

문자열의 첫 번째 문자를 꺼낸 뒤, 해당 문자를 문자열에서 모두 제거하고 길이 변화를 확인하는 방식입니다. 제거 후 길이가 정확히 1만 줄었다면 그 문자는 한 번만 등장한 고유 문자입니다.

s = 'tutorialspointfordeveloper'
while s != "":
    slen0 = len(s)
    ch = s[0]
    s = s.replace(ch, "")
    slen1 = len(s)
    if slen1 == slen0 - 1:
        print("First non-repeating character is:", ch)
        break
else:
    print("No Unique Character Found!")

실행 결과

First non-repeating character is: u

여기서 while 문 바깥의 else 절은 파이썬의 while-else 문법으로, 루프가 break 없이 정상적으로 종료되었을 때만 실행됩니다. 따라서 고유 문자를 찾지 못한 경우에만 "고유 문자 없음" 메시지가 출력됩니다.

보너스: collections.Counter로 더 간결하게

파이썬 표준 라이브러리의 Counter를 사용하면 방법 1의 로직을 훨씬 간결하게 표현할 수 있습니다.

from collections import Counter

def firstNonRepeatingChar(str1):
    counts = Counter(str1)
    for c in str1:
        if counts[c] == 1:
            return c
    return None

print(firstNonRepeatingChar('tutorialspointfordeveloper'))  # u

두 방법의 비교

방법 1(함수 기반): 문자열을 두 번 순회하지만 딕셔너리 연산은 평균 O(1)이므로 전체 O(n)으로, 긴 문자열이나 실시간 문자 스트림 처리에 적합합니다.
방법 2(while 루프): 코드가 직관적이지만 replace()를 호출할 때마다 새로운 문자열이 생성되므로 최악의 경우 O(n²)까지 느려질 수 있습니다.

실무나 코딩 테스트에서는 효율성이 검증된 방법 1 또는 Counter를 활용한 방식을 사용하는 것이 좋습니다.