두 개의 문자열 s와 t가 주어졌을 때, t를 왼쪽 또는 오른쪽 어느 방향으로든 정확히 2칸 회전하여 s를 만들 수 있는지 확인하는 문제입니다.
예를 들어 입력이 s = "kolkata", t = "takolka"라고 가정해 보겠습니다. 이 경우 "takolka"를 왼쪽으로 두 번 회전하면 "kolkata"를 얻을 수 있으므로 출력은 True가 됩니다.
문제 해결 접근 방식
이 문제는 다음 단계를 통해 해결할 수 있습니다.
- s와 t의 길이가 다르면 False를 반환합니다.
- right_rot과 left_rot이라는 빈 문자열을 준비합니다.
- t의 길이를 l에 저장합니다.
- left_rot은 t의 마지막 2글자(t[l-2:])와 나머지 앞부분(t[0:l-2])을 연결하여 생성합니다. 즉, 왼쪽 2칸 회전 결과입니다.
- right_rot은 t의 세 번째 글자부터 끝까지(t[2:])와 처음 2글자(t[0:2])를 연결하여 생성합니다. 즉, 오른쪽 2칸 회전 결과입니다.
- s가 right_rot 또는 left_rot 중 하나와 일치하면 True, 그렇지 않으면 False를 반환합니다.
아래 예제 코드를 통해 더 자세히 이해해 보겠습니다.
예제 코드
def solve(s, t): if (len(s) != len(t)): return False right_rot = "" left_rot = "" l = len(t) left_rot = (left_rot + t[l - 2:] + t[0: l - 2]) right_rot = right_rot + t[2:] + t[0:2] return (s == right_rot or s == left_rot) s = "kolkata" t = "takolka" print(solve(s, t))
입력
"kolkata", "takolka"
출력
True
이 알고리즘의 시간 복잡도는 O(n)이며, 여기서 n은 문자열의 길이입니다. 슬라이싱 연산과 문자열 비교가 각각 선형 시간에 수행되기 때문입니다. 공간 복잡도 역시 회전된 문자열을 저장하기 위해 O(n)이 필요합니다.