[리트코드/leetcode/python] 3. Longest Substring Without Repeating Characters

이미지를 누르면 문제 링크를 보실 수 있습니다

이미지를 누르면 문제 링크를 보실 수 있습니다

이 문제를 처음봤을 때, 최장수열과 관련한 풀이가 떠올랐습니다.

최장수열은 대표적인 DP 유형의 문제로서 기억을 하고 있기에 보자마자 DP를 활용해보고자 했습니다.

 

이 문제의 핵심은 문자열 S를 순회하면서 반복되지 않는 문자를 가지는 문자열의 최대 길이를 반환하는 것입니다.

그렇다면, 순회를 할 때 계속해서 알아야 하는 값은

• 현재 위치에서 조건에 맞는 문자열을 만들 수 있는 최장길이
• 이전에 똑같은 문자가 나왔는지에 대한 여부

로 정리할 수 있겠습니다.

 

그럼, 바로 코드를 살펴보고, 코드 해석을 해보도록 하겠습니다.

코드는 아래와 같습니다.

class Solution(object):
    def lengthOfLongestSubstring(self, s):

        if s == "":
            return 0

        dp = [1] * (len(s)+1)

        # dp = [1,1,1,1,1,1,1,1,1]
        tmp = s[0]
        for i in range(1,len(s)):
           
            if s[i] not in tmp:
                tmp += s[i]
                dp[i] += dp[i-1]

            else:
                tmp = tmp[tmp.index(s[i])+1:] + s[i]
                dp[i] = len(tmp)

        return max(dp)

먼저, DP 배열을 모두 1로 설정합니다. 문자열 S가 빈 문자열이 아니라면, 최소 최장문자열의 길이는 1을 반환하기 때문입니다. 여기서 DP배열이 나타내는 것은 문자열 S에서의 각 위치에서 만들 수 있는 최장 문자열의 길이를 저장하는 배열입니다.

 

아까 

문자열 S를 순회하되,  계속 알아야 할 것들 중에 하나가 

• 이전에 똑같은 문자가 나왔는지에 대한 여부

였습니다. 이를 알기 위해서 tmp라는 변수에 문자열을 저장해나가도록 설정했습니다.

초기설정값에는 문자열 S의 첫 문자인 S[0]을 할당해주고 시작합니다.

 

문자열 S를 돌면서 tmp에 s[i], 즉 해당 문자가 없다면, 그대로 tmp에 해당 문자 s[i]를 추가해줍니다.

반복되지 않은 문자니까 tmp를 갱신했고, 이제 만들 수 있는 최장 문자열 길이도 갱신해줘야 합니다.

현재 위치까지 만들 수 있는 최장 문자열 길이는 이전 위치까지 만들 수 있는 최장 문자열 길이에서 그대로 + 1 인데,

해당 작업을 dp[i] += dp[i-1] 로 실천해줍니다.

 

(여기서 그냥 +1 을 하면 안됩니다. 모든 dp의 배열이 1이기 때문에, dp[i] += 1을 하게 된다면

"dwf"같은 문자열 S가 입력값으로 주어진다면, dp의 값은 [1,2,2,1] 이 되게 됩니다. 우리가 원하는 값이라면, [1,2,3,1]이 되어야 하는데, 잘못된 값을 저장하기 때문에, 현재 위치의 dp[i] 값은 초기 설정할 때 1이니까 그 이전 위치에서의 값인 dp[i-1] 을 더해줘야 합니다. 그대로 문자열이 이어지니까요.)

 

그렇다면, 순회하는 문자가 순회하면서 저장된 문자열 tmp에 있다면, 어떻게 해야할까요?

그러면, 해당 문자가 처음 나온 인덱스부터 짜르면 됩니다. 이 말이 무슨 말인지 예를 들어 설명해보겠습니다.

예를 들어 "transportation" 이라는 문자열이 S로 주어졌다고 합시다. 현재 처음부터 순회를 한다고 하면, 

인덱스 i, 배열 dp, 문자열 tmp는 아래와 같은 출력값을 가지게 됩니다.

# 인덱스 i, dp, tmp 출력 순서

(1, [1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], u'tr')
(2, [1, 2, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], u'tra')
(3, [1, 2, 3, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], u'tran')
(4, [1, 2, 3, 4, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], u'trans')
(5, [1, 2, 3, 4, 5, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1], u'transp')
(6, [1, 2, 3, 4, 5, 6, 7, 1, 1, 1, 1, 1, 1, 1, 1], u'transpo')
(7, [1, 2, 3, 4, 5, 6, 7, 6, 1, 1, 1, 1, 1, 1, 1], u'anspor')
(8, [1, 2, 3, 4, 5, 6, 7, 6, 7, 1, 1, 1, 1, 1, 1], u'ansport')
(9, [1, 2, 3, 4, 5, 6, 7, 6, 7, 7, 1, 1, 1, 1, 1], u'nsporta')
(10, [1, 2, 3, 4, 5, 6, 7, 6, 7, 7, 2, 1, 1, 1, 1], u'at')
(11, [1, 2, 3, 4, 5, 6, 7, 6, 7, 7, 2, 3, 1, 1, 1], u'ati')
(12, [1, 2, 3, 4, 5, 6, 7, 6, 7, 7, 2, 3, 4, 1, 1], u'atio')
(13, [1, 2, 3, 4, 5, 6, 7, 6, 7, 7, 2, 3, 4, 5, 1], u'ation')

즉, 문자 "r"이 한 번 더 나오게 되는 인덱스 7 지점을 살펴본다면, 그 이전까지는 tmp가 "transpo" 였고 인덱스 6지점까지 만들어질 수 있는 최장 문자열의 길이는 7입니다.

 

하지만, 인덱스 7지점에서 "r"이 나옴으로써 tmp가 갱신되어야 하고, dp[7]에 자리에도 '만들어질 수 있는 최장 문자열의 길이'를 특정 값으로 저장해야 합니다.

 

문자 'r'이 나와도 그 이전에 'r'이 나온 바로 이후부터 다시 새로운 문자열로 인식하면 되니까,

먼저 "현재 순회하고 있는 문자와 같은 문자가 나온 위치 + 1" 자리부터 끝까지인 문자열을 갱신하고, 현재 바라보고 있는 문자 s[i]를 더해주면 새로운 tmp가 갱신되게 되는 셈이죠.

 

그렇게 되면, 앞선 예시에서 인덱스 7에서 tmp는 'transpo"에서 'anspor' 로 갱신되는 것이고, dp[7] 값도 새로 갱신된 tmp의 길이서부터 출발하면 되는 것입니다.

 

계속 순회를 하다가 문자 "a"가 한 번 더 나오게 되는 인덱스 9 지점을 살펴본다면, 그 이전까지는 tmp가 "ansport"인데, "nsporta"로 tmp가 갱신되고, dp[9]값도 자연스럽게 갱신됩니다.

 

이렇게, 끝까지 순회하다보면, 결국 DP배열에서 최대값이 문자열 S 안에서 만들 수 있는 최장 문자열의 길이가 됩니다.

 

이상으로, 최장 문자열과 관련한 Longest Substring Without Repeating Characters 문제를 정리해봤습니다.