문제 개요
길이가 m인 문자열에 영어 알파벳의 첫 m개 문자가 순서와 관계없이 들어 있다고 가정해 보겠습니다. 그런데 어떤 이유에서인지 문자열에서 한 글자가 사라졌습니다. 즉, 현재 문자열에는 m-1개의 문자만 남아 있는 상태입니다.
이번 글에서는 이렇게 불완전해진 문자열을 입력받아 누락된 문자를 찾아 반환하는 함수를 JavaScript로 작성해 보겠습니다.
예시 코드
다음은 누락된 문자를 찾는 함수의 구현 예시입니다.
const str = "acdghfbekj";
const missingCharacter = str => {
// 일관성을 위해 소문자로 변환
const s = str.toLowerCase();
for(let i = 97; ; i++){
if(s.includes(String.fromCharCode(i))){
continue;
}
return String.fromCharCode(i);
}
return false;
};
console.log(missingCharacter(str));
코드 동작 원리
이 코드의 핵심 아이디어는 다음과 같습니다.
- toLowerCase() — 입력 문자열을 모두 소문자로 변환하여 대소문자 차이로 인한 오류를 방지합니다.
- 아스키 코드 활용 — 영어 소문자 'a'의 아스키 코드는 97입니다. 반복문은 97부터 시작해 하나씩 증가하며 각 코드에 해당하는 문자를 순차적으로 확인합니다.
- String.fromCharCode() — 숫자형 아스키 코드를 다시 문자로 변환합니다.
- includes() — 해당 문자가 문자열에 존재하는지 검사하고, 존재하지 않는다면 그 문자가 곧 누락된 문자이므로 즉시 반환합니다.
출력 결과
콘솔에 출력되는 결과는 다음과 같습니다.
i
입력 문자열 "acdghfbekj"에는 a부터 k까지의 문자 중 'i'가 빠져 있으므로, 함수는 'i'를 정확히 찾아내 반환합니다.
성능 개선 팁
위 방식은 반복문이 진행될 때마다 includes()를 호출하므로 최악의 경우 O(m²)의 시간 복잡도를 가집니다. 문자열이 길어지면 비효율적일 수 있으며, Set을 활용하면 조회 속도를 O(1)로 만들어 전체 복잡도를 O(m)까지 개선할 수 있습니다.
const missingCharacterFast = str => {
const set = new Set(str.toLowerCase());
for(let i = 97; i < 123; i++){
if(!set.has(String.fromCharCode(i))){
return String.fromCharCode(i);
}
}
return false;
};두 방법 모두 같은 결과를 반환하지만, 입력 크기가 커질수록 Set 기반 구현이 훨씬 유리합니다. 상황에 맞게 선택해 사용하시기 바랍니다.