[백준 12891] DNA 비밀번호

슬라이딩 윈도우를 사용하여 해결할 수 있는 문제입니다.

Key Point

본 문제에서 주목할만한 점은 다음과 같습니다.

• 두 개의 포인터를 설정하고 마치 창틀에서 창문을 움직이듯이 두 포인터를 동시에 움직이며
  관찰하는 간격을 유지해갑니다.

해결방법

슬라이딩 윈도우를 사용해봅시다.
임의로 만든 DNA 문자열 길이와 비밀번호로 사용할 부분문자열의 길이가 최대 100만이므로
도합 O(n)의 방법으로 살펴보도록 하겠습니다.
추가적으로 시간을 더 줄이기 위해서, 간격을 옮길 때마다 해당 글자들을 전부 다시 살피는 게 아니라
빠진 글자와 새로 들어온 글자만을 고려하여 개수를 파악하는게 훨씬 빠릅니다.

예를 들어서 다음과 같이 주어진 문자열에서 간격 2만큼씩 살핀다고 가정해봅시다.

G A T A
| |          (간격의 위치 : G에서 A까지)

(현재 개수)
A C G T
1 0 1 0

다음 간격을 알아보기 위해 포인터들을 옮기게 되면
G 1개가 빠지고, T 1개가 새로 들어오게 되므로

G A T A
  | |        (간격의 위치 : A에서 T까지)

(현재 개수)
A C G T
1 0 0 1

G에서 1을 빼고 T에 1을 더해가는 식으로
그때그때 바뀌는 것만 고려하는 것이 효율적입니다.
그렇게 해서 문자열 끝까지 순회하면 최종적인 답이 도출됩니다.

코드는 아래와 같습니다.
문제 : 백준 12891 - DNA 비밀번호