[LeetCode] 3. Longest Substring Without Repeating Characters

Ho__sing·2023년 4월 20일

문제해결 자체 재수강

목록 보기

10/48

Intuition

반복을 피하기 위해서는 이전에 해당 문자가 나왔는지를 알아야한다. 마침, 등장할 수 있는 문자는 ASCII Table에 있는 128개가 전부이니 등장여부를 체크하는 배열을 만들 수 있다. 문자열을 돌다가 중복된 문자라면, 해당 문자가 나왔던 위치의 다음 인덱스부터 다시 문자열을 체크해주면 될 것이다.

Approach 1

예를 들어 다음과 같은 문자열이 있을 때,

a\quad b\quad c\quad a\quad p

일단 체크여부를 담을 배열 arr을 0으로 초기화시켜주고 시작한다.
i=0) if문에서 arr[s[i]]가 0인지 아닌지를 통해, a가 이전에 등장한적 있는지 체크해주고 등장한 적이 없으므로 arr['a']에 다음인덱스 1을 넣어준다. 현재까지 최대길이는 1이다.
i=1,2) b,c도 마찬가지로 진행하고 i=2일때 최대길이는 3이다.
void init(int* arr){
    for (int i=0;i<128;i++){
        arr[i]=0;
    }
}
//
int lengthOfLongestSubstring(char * s){
    int arr[128];
    init(arr);
    //
    int len=0, max=0;
    for (int i=0;i<strlen(s);i++){
        if(arr[s[i]]){
            ...
        }
        else{
            len++;
            arr[s[i]]=i+1;
            if (len>max) max=len;
        }
    }
    return max;
}

i=3) arr['a']의 값이 0이 아니므로 a는 이전에 한 번 등장했던 원소이다.
따라서, i의 값을 a가 처음 등장했던 인덱스의 바로 다음 인덱스 즉, arr['a']의 값으로 옮겨준다. 그리고 이 지점부터 다시 길이를 카운트해야하므로 arr배열을 0으로 초기화시켜주고, 길이는 1로, arr['a']에는 다음 인덱스를 넣어준다.

void init(int* arr){
    for (int i=0;i<128;i++){
        arr[i]=0;
    }
}
//
int lengthOfLongestSubstring(char * s){
    int arr[128];
    init(arr);
	//
    int len=0, max=0;
    for (int i=0;i<strlen(s);i++){
        if(arr[s[i]]){
            i=arr[s[i]];
            init(arr);
            len=1;
            arr[s[i]]=i+1;
        }
        else{
            len++;
            arr[s[i]]=i+1;
            if (len>max) max=len;
        }
    }
    return max;
}

이렇게 마지막까지 진행을 하게되면 답은 맞지만, Time Limit이 Exceeded된다.

Approach 2

조금만 생각을 해보면 한 번 반복여부를 체크한 곳은 다시 한번 체크할 필요가 없다는 것을 알 수 있다. 그래서 abcap와 같은 문자열이 있을 때, a,b,c,a순으로 보고 다시 b로 돌아가는 것이 아니라 문자열의 길이를 카운트하는 시작점만 b로 바꿔주고 p로 나아가면 되는 것이다.

반복되는 문자가 나왔을 때, 문자열 카운트 시작점을 바꿔줘야하기 때문에 각 문자의 인덱스를 담을 배열 arr을 선언해준다. 대신 인덱스를 담을 것이기 때문에 -1로 초기화시켜준다.
int lengthOfLongestSubstring(char * s){
    int arr[128];
    for (int i=0;i<128;i++){
        arr[i]=-1;
    }
	...
}

문자열을 순회하며 arr값이 0이상인 값은 인덱스가 들어있고 중복이라는 뜻이므로 따로 처리해줘야한다. 그렇지 않은 경우는 길이와 max값을 업데이트해주고 arr배열에 현재 인덱스를 넣어준다.
int len=0, max=0;
    for (int i=0;i<strlen(s);i++){
        if(arr[s[i]]>=0){
            ...
        }
        else{
            len++;
            if (len>max) max=len;
            arr[s[i]]=i;
        }
    }

중복된 문자가 나왔을 때에는 중복된 문자의 인덱스 이하인 문자열들을 -1로 초기화시켜줌으로써, 문자열을 세는 시작점을 중복이후의 문자열로 만든다. 그리고 이때 -1로 변경시킨 문자의 개수를 세서 실제 len값에서도 차감시킨다. 마지막으로는 else일때와 마찬가지로 arr배열에 현재 인덱스를 넣어준다.

int del(int* arr, int n){
    int cnt=0;
    for (int i=0;i<128;i++){
        if (arr[i]!=-1&&arr[i]<=n){
            arr[i]=-1;
            cnt++;
        }
    }
    return cnt-1;
}

int len=0, max=0;
    for (int i=0;i<strlen(s);i++){
        if(arr[s[i]]>=0){
            int cnt=del(arr,arr[s[i]]);
            len-=cnt;
            arr[s[i]]=i;
        }
        else{
            len++;
            if (len>max) max=len;
            arr[s[i]]=i;
        }
    }

Solution

int del(int* arr, int n){
    int cnt=0;
    for (int i=0;i<128;i++){
        if (arr[i]!=-1&&arr[i]<=n){
            arr[i]=-1;
            cnt++;
        }
    }
    return cnt-1;
}

int lengthOfLongestSubstring(char * s){
    int arr[128];
    for (int i=0;i<128;i++){
        arr[i]=-1;
    }

    int len=0, max=0;
    for (int i=0;i<strlen(s);i++){
        if(arr[s[i]]>=0){
            int cnt=del(arr,arr[s[i]]);
            len-=cnt;
            arr[s[i]]=i;
        }
        else{
            len++;
            if (len>max) max=len;
            arr[s[i]]=i;
        }
    }

    return max;
}

Complexity

Time Complexity : 문자열을 한 번 순회하고 그 과정에서 128개의 arr을 확인한다. $128n$ 이므로 $O(n)$ 이다.
Space Complexity : $O(n)$

교수님 풀이

내가 앞에서 설명했던 '문자열의 길이를 세기 시작하는 지점'을 실제 변수로 만들고 문자열을 읽어나가는 투포인터로 문제를 풀이하셨다. 정확히는 문자열의 시작점과 끝점을 각각 변수로 설정하고 이 포인터들로 문자열을 읽어나가면서 '끝점'-'시작점'+1로 문자열의 길이를 체크하는 방식이다.

우선 나의 arr과는 살짝 다르게 인덱스 대신에 단순히 등장여부를 담는 배열이 있다.
그리고 right 포인터는 중복되는 문자열이 나올 때까지 쭉 앞으로 나아간다.

중복되는 문자열이 나오면, 중복되는 문자열이 없어질때까지 배열의 등장여부를 변경시켜줌과 동시에, left포인터를 옮겨준다.

이번에는 c가 중복되었으므로 left가 a가 나올때까지 옮겨져야한다.

최종코드는 아래와 같다.
근데 생각해보면 어차피 코드의 logic자체가 중복된 문자가 나올때까지만 left가 이동하게 되어있어서 굳이 while문에 left<right 조건을 달 필요가 없다. 아래는 내가 다시 써본 코드다.

int lengthOfLongestSubstring(char * s){
    int check[128];
    for (int i=0;i<128;i++){
        check[i]=0;
    }

    int left=0, right=0;
    int max=0;
    for (;right<strlen(s);right++){
        while(check[s[right]]!=0) check[s[left++]]--;
        check[s[right]]++;
        if (right-left+1>max) max=right-left+1;
    }

    return max;
}

Complexity

Time Complexity : 코드를 얼핏보면 for문 안에 while문이 있어서 제곱이라고 생각할 수도 있지만, left가 for 반복문이 한 번 돈다고 초기화 되는 변수가 아니며, 아무리 많이 가봤자 n이기 때문에 $2n$ 으로 계산된다. 따라서 $O(n)$
$\\$
$\\$
+) 이렇게 시간복잡도를 분석하면서 내 코드와의 중요한 차이점을 알게되었는데, 기존의 내 코드는 매번 arr전체를 검사하여 128번씩 반복문을 돌아야하지만 교수님의 방식은 문자열에서 중복되는 문자 이전에 나온 것들에 대해서만 반복문을 돌게된다.
이 점을 내 코드에도 적용하여 기존보다 개선시켜보았다.

int del(int* arr, char* s, int n){
    int cnt=0;
    for (int i=n;i>=0;i--){
        if((arr[s[i]]==-1)||(arr[s[i]]>n)) break;
        else{
            arr[s[i]]=-1;
            cnt++;
        }
    }
    return cnt-1;
}

int lengthOfLongestSubstring(char * s){
    int arr[128];
    for (int i=0;i<128;i++){
        arr[i]=-1;
    }

    int len=0, max=0;
    for (int i=0;i<strlen(s);i++){
        if(arr[s[i]]>=0){
            int cnt=del(arr,s,arr[s[i]]);
            len-=cnt;
            arr[s[i]]=i;
        }
        else{
            len++;
            if (len>max) max=len;
            arr[s[i]]=i;
        }
    }

    return max;
}