문제
문자열 s와 세 배열 indices, sources, targets가 주어진다.
k번째 교체 작업은 "s의 indices[k] 위치에서 sources[k]가 시작하면 그 부분을 targets[k]로 바꾼다"는 뜻이다.
교체 작업은 모두 원본 s 기준으로 동시에 일어나며, 교체 구간은 서로 겹치지 않는다.
s = "abcd", indices = [0, 2], sources = ["a", "cd"], targets = ["eee", "ffff"]
→ "eeebffff"접근
원본 문자열을 왼쪽부터 한 글자씩 훑으면서 결과 문자열을 새로 만든다.
- 현재 위치
i를 가리키는 교체 작업k가 있고, 실제로s가i에서sources[k]로 시작하는지 확인한다. - 매칭되면
targets[k]를 붙이고i를sources[k]길이만큼 건너뛴다. - 매칭되지 않으면
s[i]를 그대로 붙인다.
새 문자열에 붙여 나가기 때문에 교체 후 길이가 달라져도 원본 인덱스가 어긋나지 않는다.
코드
function findReplaceString(s: string, indices: number[], sources: string[], targets: string[]): string {
let replaced = '';
for (let i = 0; i < s.length; i++) {
const n = indices.findIndex((idx, k) => idx === i && s.startsWith(sources[k], i));
if (n >= 0) {
replaced += targets[n];
i += sources[n].length - 1;
} else {
replaced += s[i];
}
}
return replaced;
}시간 복잡도는 O(|s| × |indices|)다. 제약이 |s| ≤ 1000, |indices| ≤ 100이라 충분하다.
틀렸던 포인트
1. 인덱스 혼동
루프 변수 i는 문자열 위치이고, sources·targets는 indices 배열의 칸 번호 k로 꺼내야 한다. sources[i]로 쓰면 엉뚱한 값을 읽는다.
2. 매칭 실패 시 글자 누락
sources[k]가 안 맞을 때 continue로 빠지면 원본 글자가 결과에서 사라진다. 교체 위치여도 매칭이 안 되면 s[i]를 그대로 붙여야 한다.
3. 0은 falsy
Map으로 위치→k를 만들고 if (k && ...)로 검사하면 k === 0인 첫 번째 작업이 통째로 무시된다. k !== undefined로 써야 한다.
4. 같은 위치의 중복 작업
indices = [2, 2, 3]처럼 같은 위치가 여러 번 나올 수 있다. 위치→k를 Map에 담으면 마지막 k만 남아 앞의 작업을 검사하지 못한다.
findIndex로 "위치가 같고 실제로 매칭되는 k"를 직접 찾으면 이 문제가 사라진다. 구간이 겹치지 않는다는 조건 덕분에 매칭되는 k는 최대 하나다.
