프로그래밍 면접 문제 15: First Non Repeated Character in String
프로그래밍 면접 문제 15: First Non Repeated Character in String
이 글은 블로그 http://www.ardendertat.com/의 프로그래밍 면접에 대한 글을 번역한 글입니다.
이전글 – 프로그래밍 면접 문제 14: Check Balanced Parentheses
가장 일반적인 면접 문제 중 하나인 “주어진 문자열에서 처음으로 반복되지 않는 (고유한) 문자 찾기” 문제입니다.
이 문제는 해시테이블(HashTable)의 효율적 사용법을 보여줘야하는 문제입니다. 해시테이블에 저장된 문자열을 왼쪽에서 오른쪽으로 확인해가면서 각 문자의 발생 횟수를 기록합니다. 그런 다음 각 문자의 발생 횟수를 기록한 수를 확인합니다. 이 과정에서 발생 횟수가 1인 경우를 확인하면 이 문자가 첫 번째 고유한 문자이기 때문에, 이 문자를 반환합니다. 고유한 문자를 찾을 수 없는 경우에는 아무 것도 반환하지 않습니다. (Phython의 경우 None을 반환합니다). 코드는 다음과 같습니다.
def firstUnique(text):
counts = collections.defaultdict(int)
for letter in text:
counts[letter] += 1
for letter in text:
if counts[letter] == 1:
return letter
보시다시피 해시테이블을 사용하면 매우 간단합니다. 복잡도 O(N)을 갖는 최적의 솔루션입니다.
일반적으로 해시테이블은 수를 세는 것과 관련된 작업에서 최적의 선형 시간 복잡도를 갖는 솔루션을 얻는데 주로 사용되는 핵심 자료 구조입니다.
