(1)자료구조 ④ 슬라이딩 윈도우

 

*️⃣ 슬라이딩 윈도우

 

 2개의 포인터로 범위를 지정한 다음, 범위(window)를 유지한 채로 이동(sliding)하며 문제를 해결합니다.
 투포인터 알고리즘과 매우 비슷하고 원리도 간단한 편입니다.

 

 

 

1. DNA 비밀번호

 

 

 

• 문제

Q. 평소 문자열을 이용해 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다.         DNA문자열은 모든 문자열에 등장하는 문자가 {'A','C','G''T'}인 문자열을 말한다.         예를 들어 "ACKA" 는 DNA 문자열이 아니지만, "ACCA"는 DNA 문자열이다.         이런 신비한 문자열에 완전히 매료된 민호는 임의의 DNA문자열을 만들고         만들어진 DNA 문자열의 부분 문자열을 비밀번호로 사용하기로 마음 먹었다.         하지만 민호는 이 방법에는 큰 문제가 있다는 것을 발견했다.         임의의 DNA 문자열의 부분 문자열을 뽑았을 때 "AAAA"와 같이         보안에 취약한 비밀번호가 만들어질 수 있기 때문이다.         그래서 민호는 부분 문자열에서 등장하는 문자의 개수가 특정 개수 이상이어야         비밀번호로 사용할 수 있다는 규칙을 만들었다.         예를 들어 임의의 DNA 문자열이 "AAACCTGCCAA"이고, 민호가 뽑을 부분 문자열의 길이를 4라고 가정해보자.         그리고 부분 문자열에 'A'는 1개 이상, 'C'는 1개 이상, 'G'는 1개 이상, 'T'는 0개 이상 등장해야         비밀번호로 사용할 수 있다고 가정해보자.         이때 "ACCT"는 'G'가 1개 이상 등장해야 한다는 조건을 만족하지 못해 비밀번호로 사용할 수 없지만,         "GCCA"은 모든 조건을 만족하므로 비밀번호로 사용할 수 있다.         민호가 만든 임의의 DNA 문자열과 비밀번호로 사용할 부분 문자열의 길이 그리고 {'A','C','G','T'}가         각각 몇 번 이상 등장해야 비밀번호로 사용할 수 있는지.         순서대로 주어졌을 때 민호가 만들 수 있는 비밀번호의 종류의 수를 구하는 프로그램을 작성하시오.         단, 부분 문자열이 등장하는 위치가 다르면 부분 문자열의 내용이 같더라도 다른 문자열로 취급한다.
[입력]	[출력]
1번째 줄에 민호가 임의로 만든 DNA 문자열의 길이 ㅣSㅣ 비밀번호로 사용할 부분 문자열의 길이 ㅣPㅣ (1≤ ㅣPㅣ ≤ ㅣSㅣ  ≤1,000,000)	비밀번호 종류의 개수를 출력
2번째 줄에 민호가 임의로 만든 DNA 문자열
3번째 줄에 부분 문자열에 포함돼야 할 {'A','C','G','T'}의 최소 개수
[입력]	[출력]
9 8 CCTGGATG 2 0 1 1	0
4 2 GATA 1 0 0 1	2

 

• 시간복잡도

1. P와 S의 길이가 1,000,000으로 매우 큼 2. O(n)의 시간 복잡도 알고리즘으로 문제 해결 3. 부분 문자열의 길이가 P  4. 슬라이딩 윈도우의 개념을 이용하여 문제 해결

* 슬라이딩 윈도우

 

• 풀이방법

1. 리스트S와 비밀번호 체크 리스트를 저장합니다. 2. 현재상태리스트를 만듭니다. 3. 비밀번호 체크리스트와 현재 상태 리스트를 비교하여 비밀번호 유효성을 판단합니다.     다음 윈도우를 확인할 때는 빠지는 문자열, 신규 문자열만 업데이트하며 확인합니다.

 

 

• 코드 순서

1.# 전역변수 선언     checkList(비밀번호 체크 리스트)    myList(현재 상태 리스트)    checkSecret(몇 개의 문자와 관련된 개수를 충족했는지 판단하는 변수) 2. # 함수 선언     myadd(문자 더하기 함수):           myList에 새로운 값을 더하고 조건에 따라 checkSecret 값 업데이트       myremove(문자 빼기 함수):          myList에 새로운 값을 제거하고 조건에 따라 checkSecret 값 업데이트 3. # 메인코드      S (문자열 크기) P (부분 문자열 크기) A (문자열 데이터)     checkList 받기     checkList를 탐색하여 값이 0인 데이터의 개수만큼 checkSecret 값 증가     #값이라는 것은 비밀번호 개수가 이미 만족되었다는 뜻     P 범위(0 ~ P - 1) 만큼 myList 및 checkSecret에 적용하고, 유효한 비밀번호인지 판단 4. for i를 P에서 S까지 반복:     j 선언 ( i - P )     # 이 부분은 myadd, myremove 함수로 별도 구현     한 칸씩 이동하면서 제거되는 문자열과 새로 들어오는 문자열을 처리     유효한 비밀번호인지(checkSecret == 4) 판단해 결괏값을 업데이트 5. 결괏값 출력

 

 

• 정답

checkArr = [0] * 4          myArr = [0] * 4          checkSecret = 0          # 함수 정의          def myadd(c): #새로 들어온 문자를 처리하는 함수              global checkArr,myArr,checkSecret              if c == 'A':                  myArr[0] += 1                  if myArr[0] == checkArr[0]:                      checkSecret += 1              elif c == 'C':                  myArr[1] += 1                  if myArr[1] == checkArr[1]:                      checkSecret += 1              elif c == 'G':                  myArr[2] += 1                  if myArr[2] == checkArr[2]:                      checkSecret += 1              elif c == 'T':                  myArr[3] += 1                  if myArr[3] == checkArr[3]:                      checkSecret += 1          def myremove(c): #제거되는 문자를 처리하는 함수              global checkArr, myArr, checkSecret              if c == 'A':                  if myArr[0] == checkArr[0]:                      checkSecret -= 1                  myArr[0] -= 1              elif c == 'C':                  if myArr[1] == checkArr[1]:                      checkSecret -= 1                  myArr[1] -= 1              elif c == 'G':                  if myArr[2] == checkArr[2]:                      checkSecret -= 1                  myArr[2] -= 1              elif c == 'T':                  if myArr[3] == checkArr[3]:                      checkSecret -= 1                  myArr[3] -= 1          S, P = map(int, input().split())          Result = 0          A = list(input())          checkArr = list(map(int, input().split()))          for i in range(4):              if checkArr[i] == 0:                  checkSecret += 1          for i in range(P):  #초기 P 부분 문자열 처리 부분              myadd(A[i])          if checkSecret == 4: #4자릿수와 관련된 크기가 모두 충족될 때 유효한 비밀번호              Result += 1          for i in range(P, S):              j = i - P              myadd(A[i])              myremove(A[j])              if checkSecret == 4:                  Result += 1          print(Result)
[입력]	[출력]
9 8 CCTGGATG 2 0 1 1	0
4 2 GATA 1 0 0 1	2

 

 

2. 최솟값 찾기1

 

• 문제

Q. N개의 수 A₁ , A₂ , ..., Aɴ 과 L이 주어진다.           Di = Aì -L+1 ~ Aì 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오.           이때, i ≤ 0 인 Aì 는 무시하고 D를 구해야 한다.
[입력]	[출력]
첫째 줄에 N과 L이 주어진다. (1 ≤ L ≤ N ≤ 5,000,000) 둘째 줄에는 N개의 수 Aì 가 주어진다. (-109 ≤ Aì ≤ 109)	첫째 줄에 Dì 를 공백으로 구분하여 순서대로 출력한다.
[입력]	[출력]
12 3 1 5 2 3 6 2 3 7 3 5 2 6	1 1 1 2 2 2 2 2 3 3 2 2

 

mydeque

A₁

A₂

A₃

A₄

A₅

Aɴ

 

10,  5

12,  6

 

6,  2

7,  3

8,  7

11,  2

 

1

1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 2, 2

 

3 < 2 : 작으니까 둠

 

원도우 크기에서 벗어나 삭제

 

• 시간복잡도

1. 윈도우의 범위는 i-L+1부터 i 까지 2. 일반적인 정렬은 O(nlongn)의 시간복잡도를 가지므로 N과 L의 최대범위가 5,000,000인 문제서는 정렬(sort)를 사용할 수 없음 3. O(n)의 시간복잡도로 해결 4. 우선 덱의 구조를 알아야 할 필요성이 있음.

• 풀이방법

1. 덱에서는 (인덱스, 숫자) 형태의 노드를 클래스로 구현하여 저장 2. 새노드 (3, 2)가 덱에 저장되는 과정 최솟값 : (1,1)    --->   1    3. 계속해서 새 노드(4, 3) 추가 최솟값 : (3, 2)   --->   2 4. 전체 과정

 

 

• 코드 순서

1. N(데이터의 개수)L(최소값을 구하는 범위)     mydeque(데이터를 담을 덱의 자료구조)     now(주어진 숫자 데이터를 가지는 리스트) 2. for N만큼 반복:          덱의 마지막 위치에서부터 현재 값보다 큰 값은 덱에서 제거          덱의 마지막 위치에 현재 값 저장          덱의 1번째 위치에서부터 L의 범위를 벗어난 값(now index-L <= index)을 덱에서 제거          덱의 1번째 데이터 출력

 

• 정답

from collections import deque          N, L = map(int, input().split())          mydeque = deque()          now = list(map(int, input().split()))          for i in range(N):              while mydeque and mydeque[-1][0] > now[i]:                  mydeque.pop()              mydeque.append((now[i],i))              if mydeque[0][1] <= i - L: # 범위에서 벗어난 값은 덱에서 제거                  mydeque.popleft()              print(mydeque[0][0], end=' ')
[입력]	[출력]
12 3 1 5 2 3 6 2 3 7 3 5 2 6	1 1 1 2 2 2 2 2 3 3 2 2