두 문자열 s와 t가 주어졌을 때, k번 이하의 이동으로 s를 t로 변환할 수 있는지 확인하는 프로그램을 만들어 보겠습니다. i번째 이동에서는 아래 두 가지 작업 중 하나를 수행할 수 있습니다.
- s에서 아직 이전 이동에서 선택되지 않은 인덱스 j(1부터 시작하며 1 ≤ j ≤ s의 길이)를 하나 골라, 해당 위치의 문자를 정확히 i번 시프트합니다.
- 아무 작업도 수행하지 않고 그대로 둡니다.
여기서 '시프트'란 문자를 알파벳 순서상 다음 문자로 바꾸는 것을 의미합니다. 예를 들어 'a'는 'b'가 되고, 'z'는 다시 'a'로 순환합니다. 따라서 문자를 i번 시프트한다는 것은 이 연산을 i번 반복 적용하는 것을 뜻합니다.
예를 들어 입력이 s = "poput", t = "vwput", k = 9라고 해보겠습니다. 이 경우 출력은 True가 됩니다. i = 6일 때 'p'를 6번 시프트하여 'v'로 만들고, i = 8일 때 'o'를 8번 시프트하여 'w'로 만들 수 있기 때문입니다.
문제 해결 접근 방법
이 문제의 핵심은 i번째 이동에서 정확히 i번의 시프트만 수행할 수 있다는 점입니다. 따라서 특정 문자를 변환하려면 필요한 시프트 횟수(diff)와 i ≡ diff (mod 26)를 만족하는 이동 번호 i가 존재해야 하며, 각 인덱스는 한 번만 사용할 수 있습니다.
해결 단계는 다음과 같습니다.
- s와 t의 길이가 다르면 False를 반환합니다.
- count 배열을 만듭니다. 각 원소는 0부터 25까지의 i에 대해 min(1, k - i + 1) + (k - i) // 26 값을 가지며, 이는 시프트 차이가 i일 때 사용 가능한 이동 횟수를 의미합니다.
- s의 각 문자 c1과 t의 대응 문자 c2를 비교합니다.
- c1과 c2가 다르면 diff = (ord(c2) - ord(c1) + 26) % 26을 계산합니다.
- count[diff]가 0 이하이면 False를 반환합니다.
- 그렇지 않으면 count[diff]를 1 감소시킵니다.
- 모든 문자를 확인한 후 True를 반환합니다.
이해를 돕기 위해 실제 구현 예제를 살펴보겠습니다.
예제 코드
def solve(s, t, k):
if len(s) != len(t):
return False
count = [min(1, k - i + 1) + (k - i)//26 for i in range(26)]
for c1, c2 in zip(s, t):
if (c1 != c2):
diff = (ord(c2) - ord(c1) + 26) % 26
if count[diff] <= 0:
return False
count[diff] -= 1
return True
s = "poput"
t = "vwput"
k = 9
print(solve(s, t, k))입력
"poput","vwput",9출력
True코드 설명
count 배열은 각 시프트 차이(0~25)에 대해 k번 이내에 사용할 수 있는 이동 횟수를 미리 계산해 둡니다. 예를 들어 diff = 6이고 k = 9라면, i = 6인 이동에서 한 번 변환이 가능하므로 count[6]은 1이 됩니다. 이후 문자열을 순회하면서 각 문자 쌍의 시프트 차이를 계산하고, 해당 차이를 만들 수 있는 이동이 남아 있으면 하나 소모하는 방식으로 문제를 해결합니다. 이 알고리즘의 시간 복잡도는 O(n)으로, n은 문자열의 길이입니다.