이번 글에서는 문자열을 입력받아, 그 문자열 안에서 가장 먼저 반복해서 등장하는 문자의 인덱스를 반환하는 JavaScript 함수를 작성해 보겠습니다.
만약 반복되는 문자가 하나도 없다면 함수는 -1을 반환해야 합니다. 예를 들어 다음과 같은 문자열이 주어졌다고 가정해 봅시다 −
const str = 'Hello world, how are you';
위 문자열에서 문자 'l'은 인덱스 2에서 처음 등장하고 인덱스 3에서 다시 나타나므로, 함수의 반환값은 2가 됩니다.
예제 코드
다음은 Map 객체를 활용한 전체 코드입니다 −
const str = 'Hello world, how are you';
const firstRepeating = str => {
const map = new Map();
for(let i = 0; i < str.length; i++){
if(map.has(str[i])){
return map.get(str[i]);
};
map.set(str[i], i);
};
return -1;
};
console.log(firstRepeating(str));동작 원리
이 알고리즘은 다음과 같은 순서로 동작합니다 −
1. 각 문자가 처음 등장한 인덱스를 저장할 Map 객체를 생성합니다.
2. 문자열을 처음부터 끝까지 한 글자씩 순회하면서, 이미 Map에 존재하는 문자를 만나면 그 문자가 처음 등장했던 인덱스를 즉시 반환합니다.
3. 아직 Map에 없는 문자라면 현재 인덱스와 함께 저장합니다.
4. 끝까지 순회했는데도 반복 문자를 찾지 못했다면 -1을 반환합니다.
출력 결과
콘솔에 출력된 결과는 다음과 같습니다 −
2
이 풀이는 문자열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 최악의 경우 모든 문자를 Map에 저장해야 하므로 공간 복잡도 역시 O(n)입니다. 덕분에 긴 문자열에서도 효율적으로 동작합니다.