문자열에서 가장 먼저 등장하는 고유 문자(중복되지 않은 문자)의 인덱스를 찾는 것은 코딩 테스트와 면접에서 자주 출제되는 대표적인 문제입니다. 이번 글에서는 C#의 내장 함수를 사용하지 않고, 배열 카운팅 기법만으로 이 문제를 해결하는 방법을 알아보겠습니다.
핵심 아이디어
해결 방식은 매우 직관적입니다. 알파벳 소문자는 총 26개이므로, 크기 256의 정수형 배열을 하나 생성하여 각 문자의 등장 횟수를 저장합니다.
구체적인 절차는 다음과 같습니다.
1. 크기가 256인 빈 배열을 새로 만듭니다.
2. 문자열 전체를 한 글자씩 순회하면서 해당 문자에 대응하는 배열 요소의 값을 1씩 증가시킵니다.
3. 모든 문자의 개수를 센 후, 다시 문자열을 처음부터 순회하면서 개수가 정확히 1인 첫 번째 문자를 찾습니다.
4. 그 문자의 인덱스를 반환하고, 고유 문자가 존재하지 않으면 -1을 반환합니다.
동작 원리 예시
예를 들어 문자열 "aabccd"가 있다고 가정해 보겠습니다.
aabccd → 각 문자별 개수: a=2, b=1, c=2, d=1
개수가 1인 문자는 b와 d이며, 이 중 문자열에서 가장 먼저 나타나는 것은 b입니다. 따라서 결과로 b의 인덱스인 2를 반환하게 됩니다.
C# 구현 코드
using System;
namespace ConsoleApplication{
public class Arrays{
public int ReturnIndexOfFirstUniqueCharachter(string s){
int index = -1;
int[] arrayValues = new int[256];
// 1단계: 각 문자의 등장 횟수 계산
for (int i = 0; i < s.Length; i++){
int value = s[i] - 'a';
arrayValues[value] += 1;
}
// 2단계: 개수가 1인 첫 번째 문자 찾기
for (int i = 0; i < s.Length; i++){
int value = s[i] - 'a';
if (arrayValues[value] == 1){
index = i;
break;
}
}
return index;
}
}
class Program{
static void Main(string[] args){
Arrays a = new Arrays();
Console.WriteLine(a.ReturnIndexOfFirstUniqueCharachter("bookisgreat"));
Console.ReadLine();
}
}
}코드 설명
1단계 – 문자 개수 세기: s[i] - 'a' 연산을 통해 각 문자를 0부터 시작하는 배열 인덱스로 변환합니다. 예를 들어 'a'는 0, 'b'는 1에 해당하며, 이 값을 인덱스로 사용해 arrayValues 배열에서 해당 문자의 등장 횟수를 증가시킵니다.
2단계 – 고유 문자 탐색: 문자열을 다시 처음부터 순회하면서, 현재 문자의 개수가 1이라면 그 위치가 곧 첫 번째 고유 문자의 인덱스입니다. 이때 break 문으로 반복을 즉시 종료하여 불필요한 연산을 줄입니다.
예외 처리: 초기값이 -1로 설정되어 있으므로, 문자열에 고유 문자가 하나도 없는 경우에는 -1이 그대로 반환됩니다.
실행 결과
입력 문자열 "bookisgreat"의 경우 각 문자의 개수는 다음과 같습니다.
b=1, o=2, k=1, i=1, s=1, g=1, r=1, e=1, a=1, t=1
개수가 1인 첫 번째 문자는 맨 앞의 'b'이므로, 프로그램은 다음과 같은 결과를 출력합니다.
0
성능 분석
이 방법의 시간 복잡도는 O(n)입니다. 문자열을 최대 두 번 순회하지만, 두 번째 순회는 일반적으로 첫 번째 고유 문자를 만나면 조기 종료되므로 실제 비용은 더 낮습니다. 공간 복잡도는 항상 256 크기의 고정 배열 하나만 사용하므로 O(1)로 일정합니다.
마무리
내장 함수나 LINQ, 딕셔너리 같은 컬렉션 없이도 단순한 정수 배열 하나만으로 첫 번째 고유 문자의 인덱스를 효율적으로 구할 수 있습니다. 이러한 배열 카운팅 기법은 아스키 코드 범위의 문자를 다루는 다양한 문자열 문제에 널리 활용되므로, 로직을 잘 익혀두면 여러 상황에서 유용하게 사용할 수 있습니다.