[BOJ][12891번] DNA 비밀번호

안녕하세요 Dibrary입니다.

이번에는 백준의 12891번 문제를 통해 '슬라이딩 윈도우'방법을 알아보겠습니다.

12891번: DNA 비밀번호

 

---

위 문제는 사실 모든 경우의 수를 따져보아도 구할 수 있습니다.
문제는, 주어진 문자열의 길이가 100만까지 가능하니까 해당 방법은 쓸 수 없다는 것이죠.

 

그러면 '모든 경우의 수를 따지지 않아도 될까?' 라는 생각이 떠오르실텐데, 네. 가능합니다.
문제에 이런 조건이 있기 때문이죠, 

위 예시를 통해 뽑을 때, 항상 '순서대로 붙어있는 채로'뽑는다는 것을 알 수 있습니다.

문제를 참 잘 읽어야 한다는 것을 이 문제에서 다시 생각해 보게 됩니다. 헣

 

그럼 이제 간단합니다.

계속 1칸씩 이동해서 확인해보면서 조건에 맞는지만 보면 되니까요.

이런식으로 말이죠.

 

---

제출한 코드는 아래와 같습니다.

기본 입력값을 받은 후에, start로 처음부터 P길이만큼을 먼저 담아둡니다.

당연히 start 구간도 해당이 되는지 먼저 따져보는 것이죠. (start 변수 바로 밑의 for문) 근데, 따져볼 때 어떻게 따지느냐~

먼저 tmp라는 사전을 만들어서 각 ACGT의 갯수를 담습니다. 그리고, 그 갯수가 입력된 조건 a,c,g,t에 부합하는지 확인하고, 맞다면 cnt를 1만큼 높입니다.

start에 대한 처리는 끝났고, 그 다음에 for문을 통해서 나머지 전체 구간을 확인하는 겁니다. 근데, tmp -=1, tmp += 1이 있죠?

슬라이딩 윈도우가 이 부분에서 적용된 겁니다. 
1칸 오른쪽으로 이동하면, 기존의 구간에 비해서 1개가 추가되고, 1개는 빠져나가게 되니까요.

 

붙어있는 것들을 살펴보되, 조건에 부합하는지를 따져볼때 단순히 1회 순회만으로 확인할 수 있는 '슬라이딩 윈도우'였습니다.