[알고리즘] sliding window, two pointer (python)
투포인터, 슬라이딩 원도우를 혼용해서 쓰는데 알고리즘에서는 보통 투포인터로 사용하는 것 같다
헷갈렸던 문법
Copy codel = Counter(['a', 'b', 'c', 'a'])
compare = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j']
missing = 4
for component in compare:
missing -= l[component]
print(l)
print(missing)
counter에는 {‘a’: 2, ‘b’: 1, ‘c’: 1}가 들어있으니
당연히 missing은 반복문이 끝난 후 0이 된다.
Copy codefrom collections import Counter
l = Counter(['a', 'b', 'c', 'a'])
compare = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j']
missing = 4
for component in compare:
missing -= l[component] > 0
print(l)
print(missing)
Counter({‘a’: 2, ‘b’: 1, ‘c’: 1})
3
Counter({‘a’: 2, ‘b’: 1, ‘c’: 1})
2
Counter({‘a’: 2, ‘b’: 1, ‘c’: 1})
1
component에 ‘a’, ‘b’, ‘c’가 들어갔을 때 결과이다.
양수일 경우 해당 값을 빼는 것이 아니라 -1만 해주는 결과가 나왔다
missing -= 1 if component in l else missing
기능을 수행하는 것과 같다
leetcode 76. Minimum Window Substring
문자열 s, t가 주어지는데 t를 포함하는 최소 문자열을 s에서 찾는 문제
Copy codeclass Solution:
def minWindow(self, s: str, t: str) -> str:
need = Counter(t)
start = end = left = 0
missing = len(t)
for right, char in enumerate(s, 1): # 오른쪽 포인터를 움직이다가
missing -= need[char] > 0
need[char] -= 1
if missing == 0: # 다 찾았으면 왼쪽 포인터를 움직인다
# need에서 양수가 되면 왼쪽 포인터를 그만 움직여야 하니까 0이 된 순간 탈출 -> start, end에 현재 포인터값 기록
# Counter need에서
# 양수일때 : 필요함(오른쪽 포인터 움직임) / 음수일때 : 필요보다 더 있다(왼쪽 포인터를 계속 움직일 수 있다) / 0일때 : 왼쪽 포인터를 그만움직이는 경계값
# t에 없는 문자도 need에 기록중이지만 t에 포함이 안되어 있으면 양수가 될 수 없다
# t에 없는 문자는 0이 될수는 있지만 0이 된 순간 왼쪽 포인터를 움직일 때 다시 나올 수 없기 때문에 탈출 후 기록하지 않으므로 괜찮..
while left<right and need[s[left]] < 0:
need[s[left]] += 1
left += 1
# while 탈출했으므로 필요한 문자를 버리기 직전
if end == 0 or right-left <= end-start:
start, end = left, right
# 현재 시작과 끝을 기록 후 왼쪽 포인터값을 버린다(오른쪽 포인터를 이동)
# 어떤 문자가 필요한지(need에서 양수), missing += 1
need[s[left]] += 1
left += 1
missing += 1
return(s[start:end]) # 1부터 시작했으므로 슬라이싱 할때 +1 x
혼자 푸는데 실패했고 코드가 길지는 않지만 counter의 음수값과 0일때 경계값이 헷갈려서 이해하기 힘들었다..
백준 20437 문자열 게임2
문자열 w가 주어지고 어떠한 문자든 상관없이 k개가 포함된 최소, 최대 문자열 길이 출력하는 문제이다.
단 해당 문자열에 딱 k개만 포함
위에 leetcode의 문제를 이해했다는 기쁨으로 인해 무지성 투포인터로 풀기를 해버려 엄청나게 많은 시간을 썼다..
Copy codedef window(w,k):
tr_f = False
ans = 10001
left = 0
cnt = Counter()
for right, char in enumerate(w, 1):
cnt[char] += 1
if cnt[char] == k:
while left < right and cnt[char]==k:
left += 1
cnt[w[left]] -= 1
if ans > right-left:
ans = right-left
tr_f = True
return (tr_f, ans)
def window2(w,k):
tr_f = False
ans = -1
left = 0
cnt = Counter()
for right, char in enumerate(w, 1):
cnt[char] += 1
if cnt[char] == k:
prev_cnt = Counter(cnt)
prev_left = left
while left < right and cnt[char] == k:
left += 1
cnt[w[left]] -= 1
if ans < right - left:
ans = right - left
tr_f = True
else:
left = prev_left
cnt = prev_cnt
return (tr_f, ans)
t = int(input())
for _ in range(t):
w = str(input())
k = int(input())
tr, ans = window(w,k)
tr2, ans2 = window2(w,k)
if not tr or not tr2:
print(-1)
else:
print(ans, ans2)
효율적이지도 않고 맞지도 않는다..
틀리는 이유는 오른쪽 포인터를 두고 왼쪽 포인터를 움직이면서 최대 길이의 문자열을 지나치게 된다.
EX) w = superaquatorndado k = 2 일때
최대 길이인 raquator를 a를 탐색하며 지나가 버린다
블로그가 처음이라 글외에 설명을 어떻게 해야 할지 모르겠다..
아이패드를 살 좋은 명분인가..?
정확히 내가 필요한 문자가 무엇인지 알고 있을 때는 leetcode 방법이 좋을 수 있겠지만 집착을 버리고 다시 생각해 보니 해결할 수 있었다..
Copy codeimport sys
input = sys.stdin.readline
from collections import Counter, defaultdict
t = int(input())
for _ in range(t):
w = str(input())
k = int(input())
cnt = Counter(w)
idx_dir = defaultdict(list)
tr_f = False
for idx, char in enumerate(w):
if cnt[char] >= k:
tr_f = True
idx_dir[char].append(idx)
if tr_f:
ans1 = 10001
ans2 = -1
for idx_lst in idx_dir.values():
for i in range(len(idx_lst)-k+1):
ans1 = min(ans1, idx_lst[i + k - 1] - idx_lst[i])
ans2 = max(ans2, idx_lst[i + k - 1] - idx_lst[i])
print(ans1+1, ans2+1)
else:
print(-1)
결국 Counter를 이용해서 k개 이상 나온 문자의 인덱스를 딕셔너리로 저장
k칸만큼 떨어진 딕셔너리 value들끼리 길이 비교
인덱스끼리 뺄셈 했으므로 +1한 값을 출력
사실 이 문제는 마지막 답을 구할 때 슬라이딩 윈도우를 살짝 사용해서 슬라이딩 윈도우라고 하기 애매 한 것 같다
백준 1806 부분합
길이가 n인 수열, 연속된 부분합 중 s이상이 되는 것 중 최소 길이 출력
Copy codeimport sys
input = sys.stdin.readline
n, s = map(int, input().split())
l = list(map(int, input().split()))
ans = float('inf')
left = 0
temp = 0
for right in range(n):
temp += l[right]
if temp < s:
continue
while left <= right and temp >= s:
temp -= l[left]
left += 1
left -= 1
temp += l[left]
ans = min(right-left+1, ans)
print(0) if ans == float('inf') else print(ans)
left, right 투포인터를 사용해서 탐색
부분합이 s이상이면 right를 멈추고 left를 움직인다.
while 탈출할때 left가 한칸 더 가니까 탈출 후 left -= 1
간단하게 풀었고 투포인터 문제 중 가장 기본적인것같다..
백준 1522 문자열 교환
a, b로만 이루어진 문자열이 주어지고 a와 b의 위치를 최소로 교환해서 모든 a와 b가 붙어있도록 수정
단 문자열은 원형 구조이다. ex) abbbbbbbbba -> 성공
Copy codeimport sys
input = sys.stdin.readline
ass = input().rstrip()
ans = float('inf')
cnt = ass.count('a')
for i in range(len(ass)):
if i+cnt >= len(ass):
ans = min(ans, ass[i:len(ass)].count('b')+ass[0:(i+cnt)%len(ass)].count('b'))
else:
ans = min(ans, ass[i:i+cnt].count('b'))
print(ans)
처음에 rstrip을 안해서 틀렸다.
시간 단축을 위해서 sys를 사용하면 문자열을 받을 때 개행문자가 포함되니 까먹지 말자!
로직은 a의 개수만큼으로 슬라이싱해서 부분 문자열에 b가 몇개있는지 count
슬라이딩 윈도우 정석 + 리스트를 원형 자료형으로 생각하는 부분 추가
원형 구조를 해결하기 위해 그냥 % 이용해서 인덱스만 수정해 주었다
백준 1253 좋다
n개의 수가 주어지고 자기 자신을 포함하지 않는 두 수의 합으로 나타낼 수 있으면 좋다 -> 좋은 수의 개수 출력
Copy codeimport sys
input = sys.stdin.readline
from collections import Counter
n = int(input())
l = list(map(int, input().split()))
test = set(l)
cnt = Counter(l)
ans = 0
if 0 in test:
if cnt[0]>=3:
ans += cnt[0]
cnt[0] = 0
for comp in cnt:
if cnt[comp]>=2 and comp!=0:
ans += cnt[comp]
cnt[comp] = 0
for left in range(n):
for right in range(left+1, n):
if l[left] + l[right] in test:
if l[left] != 0 and l[right] != 0:
ans += cnt[l[left]+l[right]]
cnt[l[left]+l[right]] = 0
print(ans)
처음에 counter를 써야겠다 생각이 들어서 그냥 쭉 구현했다.
문제를 풀고 다른사람들의 풀이를 보니 내가 조금 독특하게 푼 것 같긴 하다..
먼저 2가지 숫자를 골라 합한 수가 배열에 있는지 test -> 있으면 개수만큼 정답에 추가
여기서는 counter와 set을 이용했다
문제가 되는 부분은 고른 숫자에 0이 있을 경우이다.
자기 자신을 포함하면 안되기 때문에 0이 있을 경우에만 따로 처리를 해 주었다.
0이 배열에 있을때
0이 3개 이상 있으면 모든 0이 좋다
그리고 0이 하나라도 있으면 0이 아닌 수가 2개이상 있으면 해당 수는 모두 좋다
0때문에 좋은수로 판명난 수는 counter = 0
문제를 해결하고 너무 비효율적이라는 것을 깨달았다..
Copy codeimport sys
input = sys.stdin.readline
from collections import Counter
n = int(input())
l = list(map(int, input().split()))
test = set(l)
cnt = Counter(l)
ans = 0
if 0 in test:
if cnt[0]>=3:
ans += cnt[0]
test.remove(0)
for comp in cnt:
if cnt[comp]>=2 and comp!=0:
ans += cnt[comp]
test.remove(comp)
for left in range(n):
for right in range(left+1, n):
temp = l[left] + l[right]
if temp in test:
if l[left] != 0 and l[right] != 0:
ans += cnt[temp]
test.remove(temp)
print(ans)
생각보다 느려서 다시 살펴봤더니 counter를 건들것이 아니라 set에서 탐색한 숫자를 지우는게 현명한 선택이었다.
일반적인 투포인터 풀이
수정 전
수정 후
백준 13144 List of Unique Numbers
Copy codeimport sys
input = sys.stdin.readline
n = int(input())
l = list(map(int, input().split()))
cnt=0
for i in range(n):
for j in range(i+1, n+1):
sliced = l[i:j]
if len(sliced) == len(set(sliced)):
cnt+=1
print(cnt)
슬라이싱 시도 -> 시간초과
Copy codecnt = n
left, right = 0, 0
while left < n:
right = left+1
num_set = set()
num_set.add(l[left])
while left<right<n:
if l[right] in num_set:
break
num_set.add(l[right])
right += 1
cnt += 1
left += 1
print(cnt)
최적화 덜된 투포인터 -> 시간초과
오른쪽 포인터를 움직이다가 걸렸을 때
왼쪽 포인터를 한칸 움직이고 다시 탐색하는게 아니라
오른쪽 포인터가 만족할때까지 왼쪽 포인터를 움직여야 한다
Copy codeimport sys
input = sys.stdin.readline
n = int(input())
l = list(map(int, input().split()))
cnt = 0
left, right = 0, 0
num_set = set()
while left < n and right < n:
if l[right] not in num_set:
num_set.add(l[right])
right += 1
cnt += right-left
else:
while l[right] in num_set:
num_set.remove(l[left])
left += 1
print(cnt)
작은 디테일이 큰 성능 차이를 만든다,,
최근에 문제가 공개되지 않아 테스트 케이스를 돌려보지는 못했지만 친구에게 문제 내용을 대충 들어서 2024 네이버 공채 코테문제를 풀어 보았는데
구현보다는 최적화를 어떻게 할 것인지에 대한 요구가 있는 것 같다..
개인적으로 요긴하게 쓰는 것이 bisect, 직접 구현한 이분탐색, 투포인터 등등.. 이니 구분해서 정리를 해 봐야겠다