파이썬으로 문자열에서 중복 문자를 제거하는 프로그램

문제 개요

문자열 s가 주어졌다고 가정해 봅시다. 우리의 목표는 이전에 이미 등장했던 문자들을 모두 제거하고, 중복이 없는 축소된 문자열을 반환하는 것입니다. 이 문제를 해결하기 위해 파이썬의 OrderedDict(순서형 딕셔너리)를 활용합니다. 이 자료구조는 문자들이 처음 등장한 순서, 즉 삽입 순서를 그대로 유지해 줍니다.

딕셔너리의 값(value)은 각 문자의 빈도수로 저장하지만, 이 문제에서는 빈도수 자체는 중요하지 않습니다. 핵심은 어떤 문자가 한 번이라도 등장했는지 여부만 확인하면 되기 때문입니다. 딕셔너리 구성이 끝나면 키(key)들만 차례대로 꺼내어 하나의 문자열로 연결(join)하면 원하는 결과를 얻을 수 있습니다.

예를 들어 입력이 s = "cabbbaadac"라면, 각 문자가 처음 등장하는 순서는 'c', 'a', 'b', 'd'이므로 출력은 "cabd"가 됩니다.

해결 접근 방법

• 1단계: 키가 삽입 순서대로 저장되는 순서형 딕셔너리 d를 생성합니다.
• 2단계: 문자열 s의 각 문자 c에 대해 다음을 반복합니다.
  • c가 아직 d에 없다면 d[c] = 0으로 초기화합니다.
  • d[c] 값을 1 증가시킵니다.
• 3단계: 딕셔너리의 키들을 순서대로 연결하여 결과 문자열을 만든 뒤 반환합니다.

예제 코드

아래 구현 예제를 통해 더 잘 이해해 보겠습니다.

from collections import OrderedDict

def solve(s):
    d = OrderedDict()
    for c in s:
        if c not in d:
            d[c] = 0
        d[c] += 1

    return ''.join(d.keys())

s = "cabbbaadac"
print(solve(s))

입력

"cabbbaadac"

출력

cabd

추가 참고 사항

참고로 파이썬 3.7부터는 일반 dict도 삽입 순서를 보장하므로, 최신 버전에서는 OrderedDict 대신 일반 딕셔너리를 사용해도 동일한 결과를 얻을 수 있습니다. 또한 이 알고리즘은 문자열을 한 번만 순회하면 되기 때문에 시간 복잡도가 O(n)으로 매우 효율적입니다.