Python으로 두 문자열을 동일하게 만드는 최소 전처리 이동 횟수 구하기

문제 설명

소문자로만 이루어져 있고 길이가 같은 두 문자열 P와 Q가 있다고 가정해 보겠습니다. 우리가 구해야 하는 것은, 아래 나열된 연산들을 적용한 뒤 문자열 P를 Q와 완전히 동일하게 만들기 위해 사전에(전처리 단계에서) 수행해야 하는 최소 이동 횟수입니다.

적용 가능한 연산

임의의 인덱스 i를 선택하여 p[i]와 q[i]를 서로 교환합니다.
임의의 인덱스 i를 선택하여 p[i]와 p[n − i − 1]을 서로 교환합니다.
임의의 인덱스 i를 선택하여 q[i]와 q[n − i − 1]을 서로 교환합니다.

참고: 인덱스 i의 유효 범위는 0 ≤ i < n입니다.

여기에 더해, 한 번의 전처리 이동으로 문자열 P 안의 문자 하나를 영어 알파벳에 속한 다른 어떤 문자로든 자유롭게 바꿀 수 있습니다.

입력 예시

P = "pqprpqp", Q = "qprpqpp"인 경우를 생각해 봅시다. 이때 정답은 4입니다. P0 = 'q', P2 = 'r', P3 = 'p', P4 = 'q'로 각각 바꾸면 P는 "qqrpqqp"가 됩니다. 그다음에는 swap(P1, Q1)과 swap(P1, P5) 연산을 순서대로 적용하는 것만으로 두 문자열을 동일하게 만들 수 있습니다.

풀이 접근 방법

핵심 아이디어는 문자열을 중심을 기준으로 좌우 대칭 위치별로 살펴보는 것입니다. 각 대칭 쌍(i, n − i − 1)에 대해 네 개의 문자 P[i], P[n − i − 1], Q[i], Q[n − i − 1]을 조사하고, 서로 다른 문자의 종류 수에 따라 해당 위치에 필요한 변경 횟수를 결정합니다. 구체적인 풀이 단계는 다음과 같습니다.

n := P의 길이로 설정하고, 결과 변수 res := 0으로 초기화합니다.
i를 0부터 n/2까지 반복하면서 다음을 수행합니다.
- 새로운 맵(my_map)을 만들고 my_map[P[i]] := 1로 설정합니다.
- P[i]가 P[n − i − 1]과 같으면 my_map[P[n − i − 1]] 값을 1 증가시킵니다.
- Q[i]가 이미 맵에 있으면 my_map[Q[i]]를 1 증가시키고, 없으면 my_map[Q[i]] := 1로 추가합니다.
- Q[n − i − 1]도 마찬가지로 맵에 있으면 값을 1 증가시키고, 없으면 1로 추가합니다.
- 맵의 크기(size), 즉 서로 다른 문자의 개수를 확인합니다.
- size가 4이면 res에 2를 더합니다.
- size가 3이면 res에 1을 더하고, P[i]가 P[n − i − 1]과 같은 경우에는 1을 추가로 더합니다.
- size가 2이면 my_map[P[i]]가 2가 아닐 때 res에 1을 더합니다.
문자열 길이 n이 홀수이면서 가운데 문자 P[n // 2]와 Q[n // 2]가 서로 다르면 res에 1을 더합니다.
최종적으로 res를 반환합니다.

파이썬 구현 예제

아래 구현을 통해 위 알고리즘이 실제로 어떻게 동작하는지 확인해 보겠습니다.

def count_preprocess(P, Q):
    n = len(P)
    res = 0
    for i in range(n // 2):
        my_map = dict()
        my_map[P[i]] = 1
        if P[i] == P[n - i - 1]:
            my_map[P[n - i - 1]] += 1
        if Q[i] in my_map:
            my_map[Q[i]] += 1
        else:
            my_map[Q[i]] = 1
        if Q[n - i - 1] in my_map:
            my_map[Q[n - 1 - i]] += 1
        else:
            my_map[Q[n - 1 - i]] = 1
        size = len(my_map)
        if (size == 4):
            res += 2
        elif (size == 3):
            res += 1 + (P[i] == P[n - i - 1])
        elif (size == 2):
            res += my_map[P[i]] != 2
    if (n % 2 == 1 and P[n // 2] != Q[n // 2]):
        res += 1
    return res

A = "pqprpqp"
B = "qprpqpp"
print(count_preprocess(A, B))

실행 결과

입력

"pqprpqp", "qprpqpp"

출력

정리

이 알고리즘은 각 대칭 위치 쌍을 한 번씩만 검사하므로 전체 시간 복잡도는 O(n)입니다. 맵에 기록된 서로 다른 문자의 개수만으로 각 쌍에 필요한 최소 변경 횟수를 판단할 수 있기 때문에, 문자열 길이가 커져도 효율적으로 답을 구할 수 있다는 점이 이 풀이의 핵심 장점입니다.