Python으로 문자열의 중복 문자 제거하기: OrderedDict를 활용한 효율적인 구현 방법

문자열 s가 주어졌을 때, 이전에 이미 등장했던 중복 문자들을 모두 제거해야 합니다. 최종 결과 문자열은 원본 문자열과 문자 순서가 동일해야 합니다.

이 문제는 삽입 순서를 유지하는 ordered dictionary(순서가 보장되는 딕셔너리)를 사용하면 간단하게 해결할 수 있습니다. 딕셔너리의 값(value)은 각 문자의 빈도수로 저장하지만, 사실 빈도수 자체는 결과에 영향을 주지 않습니다. 딕셔너리를 완성한 후에는 key 값들만 추출하여 하나로 연결하면 원하는 결과 문자열을 얻을 수 있습니다.

예를 들어 입력이 s = "bbabcaaccdbaabababc"라면, 출력은 "bacd"가 됩니다.

알고리즘 접근 방식

• 삽입 순서가 유지되는 딕셔너리 d를 생성합니다.
• 문자열 s의 각 문자 c에 대해 다음을 반복합니다:
  • c가 아직 딕셔너리에 없다면, d[c] := 0으로 초기화합니다.
  • 그리고 d[c] := d[c] + 1로 빈도수를 증가시킵니다.
• 딕셔너리의 key들을 순서대로 연결하여 결과 문자열을 만든 뒤 반환합니다.

구현 예제

아래 코드를 통해 더 자세히 살펴보겠습니다.

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 = "bbabcaaccdbaabababc"
print(solve(s))

입력

"bbabcaaccdbaabababc"

출력

"bacd"

Python 3.7부터는 일반 dict도 삽입 순서를 보장하므로, OrderedDict 대신 일반 딕셔너리나 dict.fromkeys(s)를 활용해 더 간결하게 작성할 수도 있습니다.