문제는 여기에 들어가서 보면 된다.
무려 11개월 전에 풀었던 문제인데, 복습할 겸 글을 작성한다.
제출 기록들을 보니, 이때는 알고리즘 코딩을 많이 안 해봤을 때라 혼자 시도하다가 결국 discussions에서 풀이를 찾았던 것 같다.
그중 가장 빨랐던 풀이는 아래와 같다.
class Solution(object):
def lengthOfLongestSubstring(self, s):
subs = {}
start = max_length = 0
for i, x in enumerate(s):
if x in subs:
sums = subs[x] + 1
if sums > start:
start = sums
num = i - start + 1
if num > max_length:
max_length = num
subs[x] = i
return max_length
대충 알고리즘에 대해 설명하자면, 일단 문제가 요구하는 것을 정확히 파악해야 한다.
"가장 긴 substring"을 구하는 것이 아니라 가장 긴 substring의 "길이"를 구해야 한다.
그래서 가장 긴 substring을 string 변수로 유지하고 있을 필요가 없다.
string 변수로 유지하는 방법도 있긴 한데, 위의 풀이보다 조금 느리다.
(궁금하다면 아래 더보기 클릭)
class Solution(object):
def lengthOfLongestSubstring(self, s):
subs = ""
max_length = 0
for x in s:
if x in subs:
if len(subs) > max_length:
max_length = len(subs)
subs = subs[subs.index(x)+1:]
subs += x
if len(subs) > max_length:
max_length = len(subs)
return max_length
그리고 주어진 string을 한 글자씩 보며 dictionary에 key는 해당 글자, value는 해당 글자의 인덱스로 넣는다.
이 dictionary는 가장 긴 substring을 구성하는 글자들을 갖고 있다.
그런데 이미 해당 글자가 dictionary에 있다면?
문제가 요구하는 "중복되는 글자가 없는" 가장 긴 substring 조건에 어긋난다.
그 말인즉슨,
'앗, 중복되는 글자가 나와버렸네. 그럼 dictionary를 초기화하고 주어진 string의 두 번째 인덱스부터 다시 시작하자!'
하면서 brute force 알고리즘으로 짤 필요가 없다는 뜻이다.
그냥 start 부분을 중복된 글자의 index부터 시작하면 된다.
한 번에 이해하기 어려운 알고리즘일 수 있다.
이해하기 어려운 부분을 댓글로 남기면 최대한 설명해보겠다.
끝!
