오늘은 String 내에서 반복이 없는 가장 긴 Substring의 길이 구하는 법에 대해 알아보도록 하겠습니다.
문제
String인 s 변수가 함수의 파라미터로 주어질 때 s의 substring 중 가장 긴 substring의 길이를 구하는 문제입니다. 예를 들면
Input: "abcabcbb"
Output: 3
Input: "bbbbb"
Output: 1
Input: "pwwkew"
Output: 3이런 식의 답이 나오면 되겠습니다.
풀이
어떤 알고리즘 문제든 그렇듯이 모든 가능성을 전부 구한 다음에 가장 긴 String을 찾으려고 하시면 안 됩니다. 방법은 substring의 시작 부분과 끝부분 인덱스를 변수로 지정하여 j를 1씩 올리다 현재 substring에 존재하는 문자가 나오면 i를 올리는 식으로 진행하면서 string.length까지 반복하시면 됩니다. 예제는 아래와 같이 되겠습니다.
const longerWay = function (s) {
const length = s.length;
const set = new Set();
// substring 윈도우의 왼쪽끝
let i = 0;
// substring 윈도우의 오른쪽끝
let j = 0;
let longest = 0;
while (i < length && j < length) {
const endChar = s[j];
if (!set.has(endChar)) {
// 캐릭터가 없을경우 세트에 추가해주고 가장 긴 길이를 갱신
set.add(s[j++]);
longest = Math.max(longest, j - i);
} else {
// 캐릭터가 있을경우 세트에서 substring 윈도우의 왼쪽 끝 캐릭터 삭제
set.delete(s[i++]);
}
}
return longest;
};위와 같이 풀게 되면 최악의 경우 O(2n)의 시간이 걸려 전체 리스트를 2번 보게 됩니다. 살짝 더 알고리즘을 최적화해서 O(n)의 퍼포먼스를 보일 수 있는데, 그 방법은 이미 지나간 캐릭터와 인덱스를 Map에 저장해두고 j를 이동시키며 똑같은 캐릭터를 만날 시 미리 Map에 저장해둔 최근 본 동일 캐릭터의 index + 1로 i를 이동시키는 겁니다. 예제는 아래와 같습니다.
const shorterWay = function (s) {
const length = s.length;
const map = {};
let longest = 0;
// substring 윈도우의 왼쪽끝
let i = 0;
// substring 윈도우의 오른쪽끝
let j = 0;
while (j < length) {
const endChar = s[j];
// Map에 substring의 오른쪽 끝 캐릭터가 이미 저장되어있을경우
// 해당 캐릭터의 인덱스 + 1 만큼 i 인덱스를 이동시킵니다.
if (map[endChar]) {
i = Math.max(map[endChar], i);
}
longest = Math.max(longest, j - i + 1);
map[endChar] = j + 1;
j++;
}
return longest;
};위와 같이 작업할 경우 O(n) 퍼포먼스를 보일 수 있어 보다 빠르게 프로그램 실행이 가능합니다.
문제는 아래 링크를 참조하였습니다.
