파이썬 알고리즘 인터뷰 📖
알아두면 유용할 알고리즘을 하나 소개해본다 !!!
슬라이딩 윈도우란 ??
고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘을 말한다. 배열이나 리스트의 요소의 일정 범위의 값을 비교할때 사용하면 매우 유용하다. 원래 네트워크에서 사용되던 알고리즘을 문제풀이에 응용한 경우라고 할 수 있다.
투 포인터와 비슷하지만 이와 구분하기 위해 일반적으로 고정 사이즈 윈도우를 사용하는 경우를 슬라이딩 윈도우로 구분하기도 한다. 또한 주로 정렬된 배열을 대상으로 하는 투 포인터와 달리 슬라이딩 윈도우는 정렬 여부에 관계없이 활용된다는 차이가 있다.
투 포인터와 함께 슬라이딩 윈도우는 알고리즘 문제 풀이에 유용하게 자주 사용되는 중요한 기법이기 때문에 잘 알아둘 필요가 있다.
코드를 보면서 천천히 이해를 해보자.
def solve_max_sum(arr, k):
# 배열과 k값이 인자로 넘어온다.
max_sum = float('-inf')
# 최대값은 마이너스 무한대로 초기화
start = 0
# 시작 인덱스를 0으로 초기화
curr_sum = 0
# 현재까지의 합도 0으로 초기화
for end, val in enumerate(arr):
curr_sum += val
# 현재까지의 합에 val값을 계속 더해줌
if end - start + 1 == k:
# 예를 들어 k가 3이라면 3개의 합이니까
# 오른쪽(end)-왼쪽(start)+1 했을 때 그 합이 k가 되면 끝남
max_sum = max(max_sum, curr_sum)
# 최대값 계속해서 갱신해주기
curr_sum -= arr[start]
# 현재까지의 합 (3개의 합이겠지?) 에다가 시작점의 원소 하나 빼줘,
# 그럼 첫번째 원소를 뺀 나머지 뒤에 2개 원소의 합이 curr_sum 이겠지.
start += 1
# 시작점 한칸 오른쪽으로 옮겨줘
return max_sum
arr = [2,3,4,1,5]
k = 3
print(solve_max_sum(arr,k))
# 출력 : 10슬라이딩 윈도우를 이용해서 풀 수 있는 문제도 같이 소개한다.
Leetcode 3번 - "중복 문자 없는 가장 긴 부분 문자열" (책 30번)
슬라이딩 윈도우를 알고나면 너무 쉬운데, 무지성으로 풀기엔 어렵다 !!
Leetcode 3. Longest Substring Without Repeating Characters
< Medium >
Given a string s, find the length of the 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", with the length of 1.
Example 3:
Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.첫번째 시도에 무지성으로 짰던 코드 ... 시간 초과가 나올 수 밖에 없다.
파이썬이 아닌 C++ 이였다면 통과할 수 있었을까 ?
list1 = []
answer = []
cnt = 0
i = 0
while i != len(s):
if s[i] not in list1:
list1.append(s[i])
cnt += 1
else:
list1.clear()
i -= 1
cnt = 0
continue
answer.append(cnt)
print(s[i], list1, i, cnt)
i += 1
return max(answer)
=> 타임초과 !!
슬라이딩 윈도우를 이용한 정답 코드 !!
s = "abcabcbb"
# 채점할 때에는 s가 주어짐 !!
ans = 0
left_cursor = 0
used = {}
for right_cursor, char in enumerate(s):
if char in used and left_cursor <= used[char]:
left_cursor = used[char] + 1
# 왼쪽 커서를 반복되는 문자의 다음 문자 인덱스에 + 1
# abcda 이면 반복되는게 a 니까 길이는 그전에 a로 부터 시작했을거 아니야
# 이 때 left 는 0 이였겠지
# left 를 0에서 1을 더해줘 그럼 뭐야 ?
# left를 (시작점) 반복되는 문자의 바로 다음 문자의 인덱스로 정해준다.
else:
# 처음 나오는 문자라면
ans = max(ans, right_cursor - left_cursor + 1)
# 중복 전까지 다른 문자가 연속된 최대 횟수
# 오른쪽 - 왼쪽 + 1 => 그 사이에 몇개가 있나 ?
used[char] = right_cursor
# value값 업데이트
# 중복됐던거는 그거의 인덱스를 다시 저장
# abcabc 에서 두번째 a 가 나왔을 때 used[a] = 3 으로 업데이트
return ans
