한 글자까지 다른 코드 위치 찾기

자바스크립트 코딩테스트 문제로 z-algorithm 주제를 연습해보세요. 난이도는 hard이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.

today hard z-algorithm 함수명: findNearMatchCodePositions 제한 시간: 500ms

문제 설명

문자열 text와 기준 코드 pattern이 주어집니다.

text의 각 시작 위치에서 길이 pattern.length만큼 자른 문자열이 pattern과 비교해 다른 문자가 0개 또는 1개라면, 그 시작 인덱스를 정답에 포함하세요.

조건을 만족하는 모든 시작 인덱스를 오름차순 배열로 반환하는 findNearMatchCodePositions 함수를 작성하세요.

제한사항

1 <= pattern.length <= 200000
0 <= text.length <= 200000
text와 pattern은 알파벳 소문자로만 이루어져 있습니다.
pattern.length가 text.length보다 크면 빈 배열을 반환합니다.
서로 다른 문자가 정확히 0개인 완전 일치도 정답에 포함합니다.
반환값은 조건을 만족하는 0-based 시작 인덱스 배열입니다.

예시

입력: text = "abxdabc", pattern = "abcd" -> 출력: [0]
입력: text = "xabcyabqabc", pattern = "abc" -> 출력: [1, 5, 8]
입력: text = "aaaaa", pattern = "aaa" -> 출력: [0, 1, 2]
입력: text = "xyz", pattern = "a" -> 출력: [0, 1, 2]
입력: text = "abxyde", pattern = "abcdef" -> 출력: []

첫 번째 예시에서 text[0..3]은 "abxd"입니다. pattern인 "abcd"와 비교하면 세 번째 문자 하나만 다르므로 시작 인덱스 0이 정답입니다.

두 번째 예시에서는 "abc"와 완전히 같은 위치 1, 8뿐 아니라 "abq"처럼 마지막 문자 하나만 다른 위치 5도 포함합니다.

힌트

각 시작 위치마다 직접 비교하면 최악의 경우 O(text.length * pattern.length)가 됩니다.
어떤 위치에서 앞에서부터 몇 글자가 같은지와, 뒤에서부터 몇 글자가 같은지를 빠르게 알 수 있으면 한 글자 불일치를 판별할 수 있습니다.
Z 알고리즘을 pattern + 구분자 + text와 reverse(pattern) + 구분자 + reverse(text) 양쪽에 적용해 보세요.

해설

이 문제는 거의 일치하는 문자열 매칭입니다. 허용되는 불일치가 한 글자뿐이므로, 어떤 시작 위치 i에 대해 아래 두 값을 빠르게 구하면 됩니다.

pattern과 text.slice(i)가 앞에서부터 몇 글자 연속으로 같은가
pattern과 text.slice(i, i + pattern.length)가 뒤에서부터 몇 글자 연속으로 같은가

앞쪽 일치 길이를 left, 뒤쪽 일치 길이를 right라고 하겠습니다. 만약 left + right >= pattern.length - 1이면 가운데에 서로 다른 문자가 많아야 하나만 남습니다. 따라서 그 위치는 정답입니다.

완전 일치인 경우에는 left가 이미 pattern.length 이상이므로 같은 조건을 자연스럽게 만족합니다.

앞쪽 일치 길이는 pattern + "#" + text에 Z 알고리즘을 적용하면 구할 수 있습니다. 시작 위치 i에 대한 값은 붙인 문자열에서 pattern.length + 1 + i 위치의 Z 값입니다.

뒤쪽 일치 길이는 문자열을 모두 뒤집어 같은 방법으로 계산합니다. 원본의 시작 위치 i에서 끝나는 구간은 뒤집힌 text 안에서는 text.length - (i + pattern.length) 위치에서 시작합니다. 이 위치의 Z 값이 원본 구간의 뒤쪽 일치 길이가 됩니다.

풀이 순서는 다음과 같습니다.

pattern.length > text.length이면 빈 배열을 반환합니다.
Z 알고리즘 함수 buildZ(s)를 준비합니다.
pattern + "#" + text의 Z 배열로 각 시작 위치의 앞쪽 일치 길이를 구합니다.
reverse(pattern) + "#" + reverse(text)의 Z 배열로 각 시작 위치의 뒤쪽 일치 길이를 구합니다.
모든 시작 위치 i에 대해 left + right >= pattern.length - 1이면 i를 결과에 넣습니다.

Z 알고리즘은 문자열 길이에 선형으로 동작합니다. 따라서 전체 시간 복잡도는 O(n + m), 공간 복잡도도 O(n + m)입니다.

코드 작성

starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.

JavaScript 에디터 로딩 중...

커스텀 테스트

함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]

아직 실행하지 않았습니다.

실행 결과