[Java] 문자열-슬라이딩 윈도우 (문자열 교환)

https://www.acmicpc.net/problem/1522

 

내가 제일 싫어하는 문자열 문제인 줄 알고 풀어봤는데 사실 문자열은 별로 관련 없고 슬라이딩 윈도우 문제였음.

 

처음에 문제 봤을 때 문자열을 서로 교환해야 되니까 자료구조로는 배열이 적합하다 해서 그냥 배열을 선택했다.

근데 사실 교환하는 로직은 문제를 푸는데 아무 관련 없다.

 

문자열이 처음과 끝이 연결되길래 원형큐인가 하고 봤는데 그것도 아니었다. 그래서 그냥 배열로 풀었다.

 

이건 그냥 문자열 길게 늘어뜨려놓고 A의 개수를 세서 처음부터 한 칸씩 움직이면서 B의 최소 개수를 세주기만 하면 된다.

(문자열의 길이가 짧아서 가능한 브루트포스 느낌)

(문자열 처음이랑 끝이 연결되니까 나머지 연산자로 한번 더 계산해 주자)

 

처음에 생각해 본 로직은 B와 B사이에 끼어있는 A의 숫자가 가장 적은 개수를 세면 답이겠거니 했는데 구현도 귀찮고 생각해 보니까 그건 아니었다.

 

결론은 문자열 문제가 아니고 슬라이딩 윈도우 문제다.