[LeetCode] 반복된 문자없는 가장 긴 Substring 찾기. O(N) Solution

나는 개발자는 아니었지만 그래도 업무에서 코딩을 어느정도는 해야 하는 직업을 갖고 있었다. 그래서 내가 구직/이직을 위해서 잡인터뷰를 하게 되면 인터뷰어가 나에게 코딩문제를 종종 묻곤 한다. 그럴 경우에 나는 보통 $O(N^2)$의 Time Complexity 가 나오는 솔루션을 답이랍시고 이야기 하고 배째라고 버티곤 한다.

인터뷰뿐 아니라 실제업무를 할때도 Complexity 따위는 고려하지 않고 그저 에러메세지 없이 계산이 돌아가기만 하면 코드 서브밋하고 집에 밥먹으러 가는 근본없는 코딩을 해가며 반백살까지 별탈없이 살아왔다.

그러다 우연히 LeetCode에서 다음과 같은 문제를 봤다. 하나의 긴 string에서 반복되지 않는 문자로만 이루어진 substring들을 다 찾아내서 그중에서 가장 긴 녀석의 사이즈를 출력하는 문제다.

Given a string s, find the lenght of longest substring without repeating characters.

Example 1:

Input: s= "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b"

Example 3

Input: s ="pwwkew"
Output: 3
Explanation: The answer is "wke". Notice that the answer must be a substring. 
             "pwke" is not a substring, but a subsequence.

문제가 재밌어 보여서 풀어보기 시작했는데 뭐 그동안 막 살아오던 사람이 어디 쉽게 변하겠는가. 해오던대로 야무지게 $O(N^2)$가 나오는 파이썬 코드를 짜서 아래와 같이 서브밋을 했다. 사실 이 문제는 내가 회사에서 보통 해야 하는 코딩 미션보다 조금 더 복잡한 수준이였다. 그래서 서브밋하기까지 시간도 좀 걸렸고 테스트를 패쓰하고 나니 나름 희열도 있었다. 이 맛에 사람들이 코딩하는게지... 하면서 말이다.

def lengthOfLongestSubstring(s: str)-> int:
	s_list = list(s)
	longest_substring = []
        
        for i in range(len(s_list)): 
            substring = [] # substring starting from the ith index
            chars = set()  # non-repeating characters in a substring
            count = 0      # size of the substring
            
            for j in range(i,len(s_list)):
                if s_list[j] in chars: # examine if there is a repeating character
                    break 
                else:                    
                    substring.append(s_list[j])
                    chars.add(s_list[j])
                    count +=1
        
            if count>len(longest_substring):
                longest_substring = substring #updating longest substring 
        
        return len(longest_substring)

근데 Runtime 결과가 충격적이다. 내가 짠 코드의 속도가 780ms이 나왔는데 그게 하위 7.86%란다. 100명중 92등정도라는건데 마음에 상처가 왔다. 그래서 생각이라는걸 해보기로 했다. 혹시 이 미션이 $O(N)$으로도 가능한건 아닐까. 저 string을 한번 흝어가는 원샷으로 longest substring이 도출되는 미라클이 가능할것인가.

하지만 안타깝게도 나 혼자만의 깊은 사색만으로는 아무런 방법을 찾을 수가 없었다. 그래서 LeetCode에서 다른 사람들의 솔루션을 찾아봤는데 Sliding Window라고 불리는 솔루션이 있었다. 그래서 솔루션 코드를 찾아보니 for loop가 정말로 하나밖에 없고 코드를 실제로 테스트 케이스들에 돌려보니 아주 빠른 Runtime으로 패쓰를 한다. 후와 정말로 $O(N)$으로 가능한거였구나. 갑자기 엄청난 호기심이 발동을 한다. 과연 누가 처음 이렇게 풀었을까. 가장 많은 vote를 받은 게시글이 처음 아이디어를 낸 사람일 가능성이 크다고 보면 구글이라는 LeetCode 닉네임을 쓰는 사람이 맨처음으로 이 솔루션을 올린 사람인것 같다.

def lengthOfLongestSubstring(s: str)-> int:
        start = maxLength = 0
        usedChar = {}
        
        for i in range(len(s)):
            if s[i] in usedChar and start <= usedChar[s[i]]:
                start = usedChar[s[i]] + 1
            else:
                maxLength = max(maxLength, i - start + 1)
                
            usedChar[s[i]] = i
        
        return maxLength

이제 이 코드를 분석한다기 보다 감상을 한번 해볼려고 한다. 사람마다 다 다른 관점에서 이 코드를 감상하겠지만 나한테는 이런 관전포인트가 있었다. 일단 이 코드는 내가 이런 미션을 눈으로 수행하려 할 때 직관적으로 사용하게 되는 방법이 전혀 아니다. 아마 그렇기 때문에 내가 이 방법을 전혀 찾을 수 없었던게 아닐까 싶다.

우리가 보통 눈으로 이 미션을 수행하면 다음과 같은 방법으로 하지 않을까 싶다(나만 그런가).

1. 주어진 string의 맨처음 문자부터 오른쪽으로 스캔을 해나가며 문자가 반복되지 않게 substring을 만들어 나간다.
2. 스캔중 같은 문자가 반복된 것이 보이면 그 이전까지 스캔한 substring의 문자의 개수를 기억해놓는다.
3. string의 두번째 문자부터 다시 오른쪽으로 스캔을 해나가는 작업을 한다.
4. 두번째 스캔에서 채굴된 substring이 첫번째 스캔에서 채굴된 substring보다 긴지 아닌지를 비교를 한다.
5. string의 마지막 문자까지 같은 작업을 반복해서 longest substing을 찾아낸다.

나의 무근본 $O(N^2)$ 코드는 위의 과정을 나름 충실하게 구현한 것이다.

하지만 고수님이 만든 $O(N)$ 코드를 보면 새로운 substring의 시작점(코드에 있는 start 라는 변수)이 single for loop의 iteration 과정에서 동시에 update가 된다. 주어진 string의 모든 문자에서 스캔을 시작하지 않고 스캔을 시작해볼 필요가 없는 문자들을 알아서 건너뛰면서 double for loop의 필요성을 없애버렸다.

가령 'a b c b d e f d g k...' 라는 문자열을 ' a '부터 스캔을 시작하면 ' a b c '라는 substring이 만들어진다. 4번째 문자가 ' b '이기 때문에 'a b c b '는 non-repeating substring이 아니기 때문에 'a b c 에서 멈추고 다음스텝으로 넘어가야 한다. 다음 스텝에서 이 $O(N)$ 솔루션은 ' b c '라는 substring을 검사하는 불필요한 과정을 건너뛴다. ' b c ' 는 먼저 만든 ' a b c '라는 substring보다 작은 substring이므로 longest substring을 찾는 미션에서는 불필요한 작업이다. 이 코드는 start 변수의 update를 통해서 ' b c ' 를 만드는 스텝을 건너뛰고 바로 ' c b d e f '를 만들어 낸다.

불필요한 문자들에 대한 스캔을 건너뛴다는 관찰만으로는 Sliding Window라는 알고리듬이 우리가 필요한 모든 substing들을 single for loop가 해결해줄 수 있다는 사실을 설명해주지는 않는다. 사실 더 중요한 관전포인트는 어떤 로직으로 start 변수가 for loop의 각 iteration마다 여러 corner case들에 흠결없이 대응해서 미션에 필요한 모든 substring들이 sampling 되는지를 따지는 것이라고 생각한다.

내 생각에 필요한 substring들의 생성로직의 key idea는 아래의 코드에 들어있는 다음의 내용인것 같다(사실 아주 concise한 코드라서 한줄한줄이 다 핵심이지만).

       if s[i] in usedChar and start <= usedChar[s[i]]:
            start = usedChar[s[i]] + 1

• 스캔시 반복되는 문자가 나타나면 start 변수값을 새로운 인덱스값으로 바꾸게 되는데 이때 반복되는 문자가 앞서 발견된 인덱스의 바로 다음 인덱스값으로 start 변수값을 바꿔서 앞서 발견된 반복되는 문자를 새로운 substring에서는 배제하는 점.

• 스캔시 반복된 문자가 나타나더라도 start 변수값이 반복된 문자의 인덱스값보다 작거나 같을 경우에만 start 변수값을 재조정하는 점. 이를 통해 그 크기를 검사해봐야 하는 모든 substring들이 빠짐없이 else 문으로 보내져서 maxLength 를 업데이트 하는데 사용이 됨.

이외에도 string의 각 문자를 usedChar dictionary의 key로 사용하고 인덱스를 value로 사용해서 반복된 문자의 확인과 start 변수의 업데이트에 둘다 사용하고 있다는 점과 for loop의 마지막 line 한줄 하나가 새로 나온 문자와 이미 나왔던 문자들에 대한 usedChar dictionary 업데이트를 동시에 담당하고 있다는 점도 재밌게(심지어 아름답게) 느껴졌다.

초등학교 시절에 피아노를 개인과외로만 배우다가 처음 교습학원이라는 곳을 가봤는데 거기서 고학년 누나의 현란한 기교를 보고 피아노라는게 저렇게 치는거였는데 우리집 피아노가 나 만나서 그동안 고생이 많다는걸 깨닫게 된 적이 있다. 오늘도 그때와 좀 비슷한 느낌이 들었다. Python이 나 만나서 그간 고생이 많았구나.

여하간 살다 살다 내가 코드에서 이렇게 심미적인 요소를 보기는 처음인거 같다. 그리하여 이 글의 썸네일로 모네의 작품을 쓰기로 했다. 모네도 아울러 고생이 많다.