두 개의 문자열 p와 q, 그리고 숫자 r이 주어졌을 때, 문자열 p의 일부 문자를 시계 방향으로 최대 r번 이동하여 q로 변환할 수 있는지 확인하는 문제입니다. 예를 들어, 'c'는 시계 방향으로 2번 이동하면 'e'가 됩니다.
만약 입력이 p = "abc", q = "ccc", r = 3이라면 결과는 True가 됩니다. 'a'를 시계 방향으로 2번 이동해 'c'로 만들고, 'b'를 시계 방향으로 1번 이동해 'c'로 만들면 총 3번의 이동이 필요하기 때문입니다.
문제 해결 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- 문자열 a와 b의 길이가 서로 다르면 False를 반환합니다.
- k가 0인데 a와 b가 같지 않다면 False를 반환합니다.
- 누적 변수 su를 0으로 초기화합니다.
- i를 0부터 a의 길이까지 반복하면서 다음을 수행합니다.
- v := b[i]의 아스키(ASCII) 코드 값 − a[i]의 아스키 코드 값
- v가 0 이상이면 su에 v를 더합니다.
- 그렇지 않으면(음수라면) su에 v + 26을 더합니다. 이는 알파벳 순환('z' 다음은 'a')을 처리하기 위함입니다.
- su가 k보다 커지면 허용된 이동 횟수를 초과한 것이므로 False를 반환합니다.
- 반복이 모두 끝나면 True를 반환합니다.
구현 예제
아래 파이썬 구현을 통해 더 자세히 이해해 보겠습니다.
class Solution:
def solve(self, a, b, k):
if len(a) != len(b):
return False
if k == 0 and a != b:
return False
su = 0
for i in range(len(a)):
v = ord(b[i]) - ord(a[i])
if v >= 0:
su += v
else:
su += v + 26
if su > k:
return False
return True
ob = Solution()
print(ob.solve("abc", "ccc", 3))
입력
"abc", "ccc", 3
출력
True
핵심 포인트 정리
- 시간 복잡도: O(n) — 문자열 길이 n에 비례하여 한 번씩 순회합니다.
- 공간 복잡도: O(1) — 추가 메모리 없이 누적 변수 하나만 사용합니다.
- 순환 처리: 음수 차이에 26을 더하는 방식으로 알파벳 끝에서 시작 부분으로 넘어가는 경우를 자연스럽게 처리합니다.
- 조기 종료: 누적 이동 횟수가 k를 초과하는 즉시 False를 반환하여 불필요한 연산을 줄입니다.