핵심 아이디어는 간단합니다. 길이 256짜리 빈 정수 배열을 하나 생성한 뒤, 문자열 전체를 한 글자씩 순회하면서 각 문자의 등장 횟수를 배열에 기록합니다. 개수 집계가 끝나면 문자열을 다시 처음부터 순회하면서 개수가 정확히 1인 첫 번째 문자를 찾아 반환하면 됩니다.
알고리즘의 동작 방식
각 문자에서 소문자 'a'의 아스키(ASCII) 값을 빼면 0부터 25 사이의 인덱스가 계산됩니다. 이 인덱스를 배열의 위치로 활용하면 알파벳별 등장 횟수를 손쉽게 저장하고 다시 조회할 수 있습니다. 시간 복잡도는 O(n), 공간 복잡도는 고정 크기 배열을 사용하므로 O(1)로 매우 효율적인 방법입니다.
예제 1
aabccd → 2 1 2 1 → 개수가 1인 첫 번째 문자를 반환합니다. 아스키 값 계산을 통해 해당 문자가 'b'임을 알 수 있습니다.
예제 2
using System;
namespace ConsoleApplication{
public class Arrays{
public char ReturnCharacterOfFirstUniqueCharacter(string s){
int index = -1;
int[] arrayValues = new int[256];
for (int i = 0; i < s.Length; i++){
int value = s[i] - 'a';
arrayValues[value] += 1;
}
for (int i = 0; i < s.Length; i++){
int value = s[i] - 'a';
if (arrayValues[value] == 1){
index = i;
break;
}
}
return s[index];
}
}
class Program{
static void Main(string[] args){
Arrays a = new Arrays();
Console.WriteLine(a.ReturnCharacterOfFirstUniqueCharacter("bbookisgreat"));
Console.ReadLine();
}
}
}출력 결과
k
입력 문자열 "bbookisgreat"에서 b와 o는 각각 두 번 등장하지만, k는 한 번만 등장하므로 첫 번째 고유 문자인 'k'가 출력됩니다.
참고: 예외 처리 팁
위 코드는 고유 문자가 하나도 존재하지 않는 경우 index가 -1로 남아 있어 런타임 예외가 발생할 수 있습니다. 실무 환경에서는 두 번째 반복문이 끝난 뒤 index가 여전히 -1인지 검사하고, 그 경우 '\0'과 같은 기본값을 반환하거나 적절한 예외를 발생시키도록 처리하는 것이 안전합니다.