중복문자제거 JavaScript 풀이

제공된 풀이의 주요 조건은 현재 인덱스와 해당 문자가 처음 나타난 인덱스를 비교하는 것입니다. 두 값이 같을 때만 결과 문자열에 문자를 붙이면 중복을 제거하면서 최초 등장 순서를 보존할 수 있습니다.

알고리즘 설계

indexOf는 문자열에서 지정한 문자가 처음 나타나는 위치를 반환합니다. 반복문의 현재 위치가 input.indexOf(input[index])와 같다면 지금 보고 있는 문자는 처음 등장한 문자입니다. 반대로 두 값이 다르면 같은 문자가 앞에 이미 있으므로 결과에 추가하지 않습니다.

이 판단을 문자열의 처음부터 끝까지 적용하면 각 문자는 처음 등장했을 때 정확히 한 번만 선택됩니다. 결과에 문자를 붙이는 순서도 입력을 순회하는 순서와 같기 때문에 별도의 정렬 없이 원래 순서가 유지됩니다.

JavaScript 풀이

Node.js 표준 입력에서 문자열을 읽고 마지막 줄바꿈만 제거합니다. replace(/r?n$/, "")는 LF와 CRLF 입력의 마지막 개행을 처리하며, 문자열 앞뒤의 실제 문자를 함께 제거하지 않습니다. 그다음 제공 코드의 indexOf 비교 로직을 그대로 적용합니다.

const fs = require("fs");

const input = fs.readFileSync(0, "utf8").replace(/r?n$/, "");
let answer = "";

for (let index = 0; index < input.length; index += 1) {
  if (input.indexOf(input[index]) === index) {
    answer += input[index];
  }
}

console.log(answer);

문자열 전체에 trim()을 적용하면 앞뒤 공백까지 제거됩니다. 이 문제의 입력은 소문자 문자열이므로 결과에는 영향이 없지만, 입력 처리의 의미를 분명하게 하기 위해 마지막 개행만 제거했습니다.

복잡도와 검증

문자열 길이를 N이라고 하면 반복문은 N번 실행됩니다. 각 반복에서 indexOf가 앞에서부터 문자를 찾으므로 최악의 경우 O(N)이 걸려 전체 시간 복잡도는 O(N²)입니다. 입력 문자열과 결과 문자열을 저장하는 데 O(N) 공간이 필요하며, 그 밖의 추가 변수는 O(1)입니다.

저장 전 코드에서 원문 예제와 경계값을 실행했으며 LF와 CRLF 입력 모두 같은 결과를 확인했습니다. 문자열 순회의 기본은 문자 찾기 JavaScript 풀이, 대소문자 처리 방식은 대문자로 통일 JavaScript 풀이에서도 이어서 확인할 수 있습니다.