프로그래밍 면접 문제 25: Remove Duplicate Characters in String
프로그래밍 면접 문제 25: Remove Duplicate Characters in String
이 글은 블로그 http://www.ardendertat.com/의 프로그래밍 면접에 대한 글을 번역한 글입니다.
이전글 – 프로그래밍 면접 문제 24: Find Next Higher Number With Same Digits
주어진 문자열에서 첫번째 나타난 문자는 유지하고 나머지 중첩된 문자는 제거하는 문제입니다. 예를 들어, ‘tree traversal’이 입력 문자열인 경우 출력 결과는 ‘tre avsl’입니다.
확인한 문자를 기록하기 위해서 검색 작업에 효율적인 자료 구조가 필요합니다. 입력이 표준 ASCII 형식을 준수한다고 보장되면, 128 크기의 불리언(boolean) 배열을 생성하고 동일한 시간에 문자의 아스키 값의 인덱스에 접근해서 검색을 수행할 수 있습니다. 하지만 입력 문자열이 유니코드(Unicode)인 경우 100K보다 더 큰 크기의 배열이 필요하며, 일반적으로 대부분 사용하지 않기 때문에 낭비가 됩니다.
Set 자료 구조는 우리가 요구하는 목적에 완벽하게 부합합니다. set 자료구조는 키를 저장하고 특정 키의 존재여부를 검색하는 기능을 제공하며 이때 소요되는 시간은 일정합니다. 따라서 문자열의 각 문자를 루프(loop)로 반복하면서, 각 반복 작업에서 set 자료 구조를 검색해서 현재 문자가 이미 존재하는지 여부를 확인합니다. set 자료구조에 해당 문자가 있는 경우, 이 문자는 이미 확인한 문자라는 의미이기 때문에 이 문자를 무시합니다. set 자료구조에 현재 문자가 없는 경우 결과에 현재 문자를 포함하고 set 자료구조에도 포함시켜 나중에 참조할 수 있도록 합니다. 다음 코드를 확인하면 이해하는 데 훨씬 수월할 것입니다.
def removeDuplicates(string):
result = []
seen = set()
for char in string:
if char not in seen:
seen.add(char)
result.append(char)
return ''.join(result)
set 자료구조는 삽입 및 검색을 O(1)의 복잡도로 제공하기 때문에, 이 알고리즘의 시간 복잡도는 O(N)이며 여기에서 N은 입력 문자열의 문자 수입니다. 이 방법은 가장 일반적인 문자열 관련 면접 문제 중 하나에 대한 최적의 해결 방법입니다.
참고: set 자료구조의 삽입 및 검색의 복잡도는 언어와 구현 방법에 따라 달라질 수 있습니다. 평균적으로 대부분 일정하지만, 최악의 경우 대수적(logarithmic)이거나 비례적으로 복잡도가 증가할 수 있습니다. 하지만 면접 환경에서는 set 자료구조의 삽입 및 검색 시간을 일정한 시간으로 가정해도 괜찮을 것으로 생각합니다.
