프로그래밍 면접 문제 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)을 갖는 최적의 솔루션입니다.
일반적으로 해시테이블은 수를 세는 것과 관련된 작업에서 최적의 선형 시간 복잡도를 갖는 솔루션을 얻는데 주로 사용되는 핵심 자료 구조입니다.

 

다음글 – 프로그래밍 면접 문제 16: Anagram Strings

RonnieJ

프리랜서 IT강사로 활동하고 있습니다. 게임 개발, C++/C#, 1인 기업에 관심이 많습니다.

답글 남기기

이메일 주소는 공개되지 않습니다. 필수 필드는 *로 표시됩니다

Please turn AdBlock off

Notice for AdBlock users

Please turn AdBlock off