[PS] 2014 Daejeon 6901 String Transformation

이 문제는 기존문자열을 목적문자열로 변환시키는데 몇번의 swap이 필요한지 묻는 문제이다.

swap은 인접한 문자끼리만 가능하다.

예를들어

aaaabbbb 가 목적문자열이고

aabbabab 가 기존 문자열일경우

aababbab 로 1번 바꾼후

aaabbbab 로 2번 바꾼후

aaabbabb 로 3번 바꾼후

aaababbb 로 4번 바꾼후

aaaabbbb 로 5번 바꾸면 목적 문자열이 된다.

위 방법은 목적 문자열과 기존 문자열을 처음부터 비교하면서

서로 다른 문자가 나올경우, 기존문자열은 현재 첨자부터

목적문자를 찾는다.

그리고 찾은 기존문자를 현재의 첨자에 삽입한다.

위 알고리즘의 시간복잡도는 n + a(검색시간) + b(배열삽입시간)

이때 배열삽입시간을 제거하기위해

실제로 배열을 밀지않고, 상대적인 첨자를 통해 답을 구할 수 도 있다.

aaaabbbb

aabbabab 가 있을때

같으면 첨자를 넘긴다. 앞의 aa는 같으므로 3번째 문자부터 비교한다.

aaaabbbb ( 목적 )

aabbabab ( 기존 )

기존 문자열에서 현재첨자에서 가장 가까운 목적문자 (3번째의 a) 를 찾으면

기존문자열의 5번째에 존재한다.

이때 a가 swap해야하는 횟수는 (찾은첨자 - 현재첨자) 이다.

그리고 찾은 a를 x로 바꾸고 a를x로 바꾼 횟수를 센다. 이것을 AX라 하겠다.

aaaabbbb ( 목적 )

aabbxbab ( 기존 )

그럼 문자열이 다음과같이 변경된다.

기존문자열 bbxbab 앞에 a가 삽입되었다고 가정한다.

그렇다면 다음과 같이 볼수있다.

aaaabbbb ( 목적 )

aabbxbab ( 기존 )

목적문자열은 4번째부터 기존문자열은 3번쨰부터 다시 위의 과정을 반복하면된다.

다만 x표를 쳐놨으므로 a가 swap 해야하는 횟수는 위의 식에 다음을 추가한다.

(찾은첨자 - 현재첨자) - AX

이런식으로 배열을 순회하면 답을 구할 수있다.

위 사실을 보았을때 기존문자열의 a는 반드시 목적문자열의 a의 위치로 움직여야 한다.

그렇다면 기존 문자열의 위치와 목적 문자열의 위치만으로 a가 움직여야할 수를 정할수 있다. (a가 올바르게 삽입되면 b는 자동으로 삽입되기 때문)

aaaabbbb 에서 a의 위치 배열은 (0,1,2,3)

aabbabab 에서 a의 위치 배열은 (0,1,4,6) 이다.

그렇다면 a가 swap 해야하는 횟수는 두 배열의 벡터합의 절대값이다.