JavaScript에서 문자열을 첫 번째이자 유일한 인수로 받는 함수를 작성해야 합니다.
이 함수는 문자열을 앞에서부터 탐색하면서 단 한 번만 등장하는 첫 번째 문자를 찾고, 그 문자의 인덱스를 반환해야 합니다.
만약 문자열에 고유한 문자가 하나도 없다면, 함수는 -1을 반환해야 합니다.
문제 예시
예를 들어, 입력 문자열이 다음과 같다고 가정해 보겠습니다.
const str = 'hellohe';
여기서 'h'는 인덱스 0과 5에, 'e'는 인덱스 1과 6에, 'l'은 인덱스 2와 3에 각각 두 번 등장합니다. 반면 'o'는 인덱스 4에 단 한 번만 나타나므로, 기대하는 출력값은 다음과 같습니다.
const output = 4;
접근 방법
이 문제는 해시 객체(연관 배열)를 활용하면 선형 시간 안에 효율적으로 해결할 수 있습니다.
- 문자열을 한 번 순회하면서 각 문자별로 등장 횟수와 처음 등장한 인덱스를 객체에 저장합니다.
- 순회가 끝난 후 저장된 데이터를 다시 확인하여, 등장 횟수가 정확히 1인 문자를 찾으면 그 문자의 인덱스를 반환합니다.
- 객체의 키는 삽입 순서가 유지되므로, 조건을 만족하는 첫 번째 문자가 곧 원본 문자열에서 가장 먼저 나오는 고유 문자입니다.
- 모든 문자가 두 번 이상 등장했다면 루프가 종료된 후
-1을 반환합니다.
이 알고리즘의 시간 복잡도는 O(n), 공간 복잡도 역시 O(n)으로, 문자열 길이에 비례하여 선형적으로 동작합니다.
구현 코드
위 접근 방식을 구현한 전체 코드는 다음과 같습니다.
const str = 'hellohe';
const firstUnique = (str = '') => {
let obj = {};
// 1단계: 각 문자의 등장 횟수와 첫 등장 인덱스를 기록
for(let i = 0; i < str.length; i++){
if(str[i] in obj){
let temp = obj[str[i]];
let x = parseInt(temp[0]);
x += 1;
temp[0] = x;
obj[str[i]] = temp;
} else {
obj[str[i]] = [1, i];
}
}
// 2단계: 등장 횟수가 1인 첫 번째 문자의 인덱스 반환
let arr = Object.keys(obj);
for(let i = 0; i < arr.length; i++){
let z = obj[arr[i]];
if(z[0] === 1){
return z[1];
}
}
// 3단계: 고유 문자가 없으면 -1 반환
return -1;
};
console.log(firstUnique(str));실행 결과
코드를 실행하면 콘솔에 다음과 같은 결과가 출력됩니다.
4
결과값 4는 문자열 'hellohe'에서 유일하게 한 번만 등장하는 문자 'o'의 인덱스와 일치합니다. 이처럼 객체를 이용한 카운팅 기법을 사용하면 문자열을 최대 두 번만 순회하면서 문제를 깔끔하게 해결할 수 있습니다.