[알고리즘 마스터] 11. 슬라이딩 윈도우

안녕하세요. 개발감자 박그냥입니다!🥔

오늘은 알고리즘 중 슬라이딩 윈도우에 대해 정리해보도록 하겠습니다.

1. 슬라이딩 윈도우 개념

10. 투포인터와 연결되는 개념입니다.

슬라이딩 윈도우 알고리즘은 2개의 포인터로 범위를 지정한 다음에, 범위를 유지한 채로 이동하며 문제를 해결합니다.

투 포인터 알고리즘과 매우 비슷하며 원리도 간단합니다. 

 

개념을 백준 문제를 통해 이해해보도록 하겠습니다.

 

2. 슬라이딩 윈도우 관련 문제풀이

2-1. 슬라이딩 윈도우 백준 문제 - 12891

인증

2-2. 문제 풀이

import sys

input = sys.stdin.readline

N, M = map(int, input().split())
A = list(input().strip())  # 개행 문자 제거
num_A, num_C, num_G, num_T = map(int, input().split())

count_list = ['A', 'C', 'G', 'T']
lst_M = [0 for _ in range(M)]

# 초기 M개의 문자에 대한 개수 계산
count_A = A[:M].count('A')
count_C = A[:M].count('C')
count_G = A[:M].count('G')
count_T = A[:M].count('T')

# 초기 M개의 문자열이 조건을 만족하는지 확인하고 카운트
if count_A >= num_A and count_C >= num_C and count_G >= num_G and count_T >= num_T:
    count = 1
else:
    count = 0

# 슬라이딩 윈도우로 문자열 탐색
for i in range(1, N - M + 1):
    # 윈도우에서 하나 빼고 새로운 문자 추가
    out_char = A[i - 1]
    in_char = A[i + M - 1]

    # 문자열에서 빠진 문자의 개수 차감
    if out_char == 'A':
        count_A -= 1
    elif out_char == 'C':
        count_C -= 1
    elif out_char == 'G':
        count_G -= 1
    elif out_char == 'T':
        count_T -= 1

    # 새로 들어온 문자의 개수 추가
    if in_char == 'A':
        count_A += 1
    elif in_char == 'C':
        count_C += 1
    elif in_char == 'G':
        count_G += 1
    elif in_char == 'T':
        count_T += 1

    # 조건을 만족하는지 확인하고 카운트
    if count_A >= num_A and count_C >= num_C and count_G >= num_G and count_T >= num_T:
        count += 1

print(count)

 

여기서 가장 중요한 개념은 in_char와 out_char 입니다. 

가장 처음의 문자열만 저장하여  A,C,G,T의 갯수를 확인하고 다음의 문자열로 갈 때에 들어오는 문자와 나가는 문자를 각각 In_char와 out_char에 저장하고 그에 따라 갯수도 같이 업데이트를 해줍니다. 매번 문자열의 갯수를 확인할 필요없이 in_char와 out_char만을 이용하여 A,C,G,T의 갯수를 확인할 수 있습니다.

시간 초과 발생

 

원래는 문자열을 매번 구하고, A,C,G,T의 갯수를 count 함수를 이용하여 계산했지만 이로 인하여 시간 초과가 발생하였고, 시간 초과 이슈를 해결하는 방법으로 in_char와 out_char을 활용하였습니다. 혹시 이해가 안되는 부분있다면 댓글 남겨 주시면 바로 답변드리겠습니다.

 

그럼 더 유익한 포스팅으로 찾아뵐게요! 개발감자였습니다 :)