solution 1
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
// 빈 문자열을 입력받은 경우 0 반환.
if(s.length === 0){
return 0;
}
let start = 0; // window 시작
let end = 0; // window 끝. end가 움직이면서 substring 내부 연산을 진행함.
let maxLength = 1; // 최대 substring 길이
let substring = ""; // window
while(start < s.length){
// window의 끝에 추가한다. 즉, window의 이동.
substring += s[end];
// 현재 추가된 문자열이 substring에 존재하지 않던 값이라면 중복이 없는 substring이다.
// 즉, 현재 추가된 문자열의 indexOf()가 substring의 맨 뒤가 나오면 된다.
// 그러나, 겹치는게 있다면 window를 늘리는게 아니라 옮겨야함.
// window 시작점과 끝점이 변경되고, length와 substring이 초기화된다.
if(substring.indexOf(s[end]) !== substring.length - 1){
start++;
end = start;
substring = "";
continue;
}
// 최대 길이 갱신
maxLength = Math.max(maxLength, substring.length);
// 만약, 주어진 문자열의 길이가 substring의 최대 길이와 같다면
// 더 이상 연산을 진행할 필요가 없기 때문에 그대로 종료.
if(maxLength === s.length){
return maxLength;
}
// window를 늘린다. 즉, substring 길이를 늘린다.
end++;
}
return maxLength;
};필자는 sliding window 알고리즘을 사용했다.
substring의 최대 길이를 구하는 것이 목적이기 때문에, 사실상 끝까지 연산을 해줘야했다.
그러나, 필자의 방법은 start 인덱스를 정하면 그 곳에서부터 만들 수 있는 substring을
최대한 만들어낸 뒤에, 다음 start로 넘어가므로
첫 start에서 최대 길의 substring을 뽑아낼 수 있었다.(가능한 경우에만)
물론, 문제의 조건이 중복값이 없는 substring이었기 때문에 이를 미리 필터링하였다.
만약, 중복값이 없는 substring인데 길이가 주어진 문자열 s와 같다면 이후로는
연산을 진행할 필요가 없기 때문에 조건문 처리를 해줬다.
이 덕분에 최초 start에 해당하는 substring에서 s와 동일한 길이가 나온다면 미리 연산을 종료할 수 있었다.
이런 경우가 아니라면 계속해서 window(정확히는 substring)의 길이를 늘려가면서 연산을 진행했다.
start : 0
substring에 들어갈 인덱스
0
0 1
0 1 2
0 1 2 3
...
=> 이 덕분에 start가 0일 때 최대 길이의 substring을 얻을 수 있고
s.length와 substring.length가 같은 경우 연산을 종료할 수 있다.만약, s의 길이와 최대 substring의 길이가 일치하지 않는다면,
이후의 연산을 지속한다.
지정했던 start를 기준으로 substring의 길이를 늘려가면서 연산을 진행해나가는 것이다.
그러나, 이 방법은 substring의 최대 길이가 s의 길이와 일치하지 않는다면
이후의 연산도 계속해서 진행해야하는 단점이 있다.
즉, substring이 길지 않은 경우에는 거의 모든 경우를 다 탐색해봐야 된다는 것이다.
어떤 경우에 더 긴 길이가 나올지 알 수 없기 때문이다.
어떻게 해야지 연산을 더 빠르게 할 수 있을까?
구해야하는 것은 substring의 최대 길이였다.
그런데 필자는 가능한 최소 길이부터 연산해나갔다.
최대 길이는 언제 나올지 모르기 때문에 계속해서 연산을 했어야했다.
그럼 이번에는 가능한 최대 길이부터 연산해보면 어떨까?
sliding window 알고리즘은 start와 end를 통해 window를 이동해나가는 것인데,
이를 반대로 하면 되지 않을까?
가능한 최대 길이부터 연산해서 내려가다가, 조건을 한번이라도 만족하는 순간,
그보다 아래의 연산은 전혀 연산할 필요가 없다.
그 때가 최대 길이의 substring이기 때문이다.
Time Limit Exceeded 1
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
if(s.length === 0){
return 0;
}
// 최대 길이부터 시작하기 때문에 start와 end는 s의 양 끝에 둔다.
let start = 0; // window 시작
let end = s.length - 1; // window 끝. end가 움직이면서 substring 내부 연산을 진행함.
let length = s.length; // 현재 substring의 길이
// 최대 길이부터 시작해서, window 길이를 고정한 채로 순회하고, 점점 window를 줄여나가기 때문에
// end가 0이 될 때까지 반복하면 된다. 모든 경우의 수를 보기 전까지는 end가 0이 되지 않기 때문이다.
outer:while(end !== 0){
let substring = s.slice(start, end + 1);
// 현재 substring에서 가장 뒤에 있는 문자의 중복 여부를 판단.
// 가장 뒤에 있으므로, indexOf로 얻은 인덱스가 가장 뒤가 아니라면 중복이 존재하는 것.
// 중복이라면 현재 substring은 더 이상 정답 후보군이 아님.
for(const str of substring){
if(substring.indexOf(str) === substring.lastIndexOf(str)){
continue;
}
// start가 0이라면 현재 크기의 window가 더이상 앞으로 이동할 수 없음을 의미.
// 따라서 window의 크기를 한칸 줄이고, end를 (s.length - 1) 인덱스로 변경한다.
// start도 크기에 맞게 변경해준다.
if(start === 0){
length--;
end = s.length - 1;
start = end - length + 1; // end - start + 1 = length
continue outer;
}
// start가 0이 아니라면 현재 길이의 window를 앞으로 더 움직일 수 있다는 것.
start--;
end--;
continue outer;
}
// 위 조건문을 통과했다면 해당 substring이 최대 길이의 substring이다.
return length;
}
// 만약 while문이 끝날 때까지 아무것도 반환되지 않았다면 답이 없는 문제거나 최소 길이인 1이 최대 substring이 된다.
return 1;
};가장 큰 substring부터 연산하도록 변경했지만, 문제는 for문이 생겨버렸다는 것이다.
가장 작은 substring부터 연산할 때는 새로 들어오는 문자에 대해서만 중복 검사를 하면 됐지만,
이 방법에서는 기존 문자열에서부터 하나씩 줄여가면서 연산하기 때문에,
문자열이 큰 덩어리로 나오게 되고(이전 방법은 최소 단위부터 쌓여갔었다),
중복 문자 검증을 위해 substring을 순회해야하는 문제가 발생했다.
그런데 아무리 생각해도 substring을 순회하지 않고서는
차례대로 쌓여나가지 않고 큰 덩어리로 나오는 문자열 내부의 중복 검증을 할 방법이 떠오르지 않는다.
그치만...연산을 최소화하기 위해서는 최대 길이부터 연산하는게 좋을 것이다.
이번에는 검증을 위해 Set 객체를 활용해볼 것이다.
평소에 배열에만 사용했던터라 문자열에도 바로 사용 가능하다는 점을 잊고 있었다.
Time Limit Exceeded 2
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
if(s.length === 0){
return 0;
}
// 최대 길이부터 시작하기 때문에 start와 end는 s의 양 끝에 둔다.
let start = 0; // window 시작
let end = s.length - 1; // window 끝. end가 움직이면서 substring 내부 연산을 진행함.
let length = s.length; // 현재 substring의 길이
// 최대 길이부터 시작해서, window 길이를 고정한 채로 순회하고, 점점 window를 줄여나가기 때문에
// end가 0이 될 때까지 반복하면 된다. 모든 경우의 수를 보기 전까지는 end가 0이 되지 않기 때문이다.
while(end !== 0){
let substring = s.slice(start, end + 1);
// Set으로 문자열 중복 검증
// Set 객체의 size와 substring의 length가 일치하지 않는다면 중복 문자열이 존재하는 것이다.
if(new Set(substring).size !== substring.length){
// start가 0이라면 현재 크기의 window가 더이상 앞으로 이동할 수 없음을 의미.
// 따라서 window의 크기를 한칸 줄이고, end를 (s.length - 1) 인덱스로 변경한다.
// start도 크기에 맞게 변경해준다.
if(start === 0){
length--;
end = s.length - 1;
start = end - length + 1; // end - start + 1 = length
continue;
}
// start가 0이 아니라면 현재 길이의 window를 앞으로 더 움직일 수 있다는 것.
start--;
end--;
continue;
}
// 위 조건문을 통과했다면 해당 substring이 최대 길이의 substring이다.
return length;
}
// 만약 while문이 끝날 때까지 아무것도 반환되지 않았다면 답이 없는 문제거나 최소 길이인 1이 최대 substring이 된다.
return 1;
};Set 객체를 사용함으로써 반복문을 줄였지만, 마찬가지로 시간 초과가 되었다.
Set 객체를 생성하는 과정이 O(n)이기 때문에 결과적으로 시간 복잡도는 동일했던 것으로 생각된다.
다른 분의 solution
var lengthOfLongestSubstring = function (s) {
let set = new Set();
let left = 0;
let maxSize = 0;
if (s.length === 0) return 0;
if (s.length === 1) return 1;
for (let i = 0; i < s.length; i++) {
while (set.has(s[i])) {
set.delete(s[left])
left++;
}
set.add(s[i]);
maxSize = Math.max(maxSize, i - left + 1)
}
return maxSize;
}이 분도 Set 객체를 사용하셨다.
sliding window 알고리즘을 사용하기 위해 두 개의 포인터를 사용했었는데,
이 분은 하나의 포인터와 Set 객체를 활용하여 sliding window를 구현하셨다.
단순히 중복 문자열 판별을 위한 Set이 아니었다!
Set 객체에 문자열을 저장해나가다가, 중복 값이 들어오는 순간
while 부분이 작동하며 window를 한 칸 옮기는 작업을 하는 것이다.
set.delete() 부분은 window의 맨 앞을 지우는 역할이 된다.
