[알고리즘] 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, 직접 구현한 이분탐색, 투포인터 등등.. 이니 구분해서 정리를 해 봐야겠다