두 개의 문자열 a와 b가 주어졌을 때, 문자열 b를 시계 방향 또는 반시계 방향으로 정확히 2칸 회전하여 문자열 a를 만들 수 있는지 판별하는 문제입니다. 예를 들어 다음과 같습니다.
입력 예제 1 −
a = google b = legoog
출력 −
True
설명 − 문자열 'google'을 시계 방향으로 2칸 회전하면 뒤의 두 글자 'le'가 맨 앞으로 이동하여 'legoog'가 됩니다. 따라서 True를 반환합니다.
입력 예제 2 −
a = tuorialst b = tutorials
출력 −
False
설명 − 문자열 'tutorials'를 어떤 방향으로 2칸 회전하더라도 'tuorialst'를 만들 수 없습니다. 따라서 False를 반환합니다.
문제 해결 접근 방식
주어진 두 문자열에 대해 이 접근 방식에서는 두 가지 경우를 고려합니다.
반시계 방향(왼쪽) 회전
시계 방향(오른쪽) 회전
먼저 두 문자열의 길이가 서로 다르면 어떤 회전을 하더라도 같아질 수 없으므로 false를 반환합니다. 반대로 두 문자열의 길이가 2 이하라면, 2칸 회전해도 원래 문자열과 동일하게 유지되므로 true를 반환합니다.
그 외의 경우에는 문자열 'b'를 반시계 방향으로 2칸 회전한 결과가 문자열 'a'와 같은지 확인하고, 같다면 true를 반환합니다. 그렇지 않으면 false입니다.
마찬가지로 문자열 'b'를 시계 방향으로 2칸 회전한 결과가 문자열 'a'와 같다면 true를, 그렇지 않다면 false를 반환합니다.
알고리즘 단계
두 입력 문자열 'a'와 'b'를 받습니다.
불리언 함수 checkRotated(string a, string b)는 두 문자열을 인자로 받아, 'b'를 반시계 또는 시계 방향으로 2칸 회전했을 때 'a'와 같아지는지 여부를 반환합니다.
문자열 'a'와 'b'의 길이를 확인합니다.
문자열 'b'를 반시계 방향으로 2칸 회전한 문자열을 구합니다.
결과 문자열이 'a'와 같은지 확인하고, 같으면 true를 반환합니다.
문자열 'b'를 시계 방향으로 2칸 회전한 문자열을 구합니다.
결과 문자열이 'a'와 같은지 확인하고, 같으면 true를 반환합니다.
어느 쪽도 일치하지 않으면 false를 반환합니다.
Java 구현 예제
public class Solution {
static boolean checkRotated(String str1, String str2) {
int len = str2.length();
// 길이가 다르면 어떤 회전으로도 같아질 수 없음
if (str1.length() != len) {
return false;
}
// 길이가 2 이하면 2칸 회전해도 원본과 동일
if (len <= 2) {
return true;
}
// 반시계 방향(왼쪽) 2칸 회전: 앞의 2글자를 뒤로 이동
String s1 = str2.substring(2) + str2.substring(0, 2);
// 시계 방향(오른쪽) 2칸 회전: 뒤의 2글자를 앞으로 이동
String s2 = str2.substring(len - 2) + str2.substring(0, len - 2);
return str1.equals(s1) || str1.equals(s2);
}
public static void main(String[] args) {
String a = "google";
String b = "legoog";
System.out.println(checkRotated(a, b) ? "True" : "False");
}
}실행 결과
위 코드를 실행하면 다음과 같은 출력이 나타납니다.
True
'legoog'를 반시계 방향으로 2칸 회전하면 앞의 두 글자 'le'가 뒤로 이동하여 'google'이 되기 때문입니다. 반면 checkRotated("tuorialst", "tutorials")를 호출하면 어느 방향으로 회전해도 두 문자열이 일치하지 않으므로 False가 출력됩니다.
복잡도 분석
이 알고리즘은 부분 문자열 추출과 문자열 비교 연산만 사용하므로 시간 복잡도는 O(n)이며, 회전된 문자열을 저장하기 위한 추가 공간 역시 O(n)입니다. 여기서 n은 문자열의 길이입니다.