회전 문자열 검사 방법

어떤 문자열이 다른 문자열의 회전 문자열인지 검사하려면 어떻게 해야 할까? 코딩 인터뷰에 많이 나올 듯 한 문제다. 트위터에서 이 문제를 보고는 잠깐 생각해 보았지만 풀이가 금방 떠오르지 않았다. 한동안 이런 종류의 퀴즈 풀이를 하지 않아서 그런 것 같다.

트위터에서 링크를 타고 들어가 블로그 글을 보니 두 가지 방법이 소개되어 있었다. 두 문자열을 s1, s2라 할 때, 첫 번째 방법은 s1을 두 번 이어붙인 문자열에서 s2가 있는지 확인한다. 즉 (s1 + s1).contains(s2)가 true면 s1이 s2의 회전 문자열임을 알 수 있다.

생각해보니 참 간단하면서 기발한 방법이란 생각이 들었다. 이렇게 간단하게 풀 수 있을 줄은 몰랐다. 그러나 면접관이 문자열 이어붙이기를 쓰지 않고 풀라고 하면 어떻게 할까? 블로그에 소개된 두 번째 방법은 안타깝지만 정답이라 하기엔 문제가 많다. 내가 찾은 문제는 다음과 같다.

• 두 문자열이 모두 빈 문자열인 경우 예외가 발생한다.
• 두 문자열이 동일한 경우에도 true를 리턴한다.
• 첫 문자가 중복해 나타나는 경우 잘못된 결과를 리턴한다.

흥미삼아 간단히 풀어보았다. 두 문자열이 같은 경우는 false를 리턴하도록 if 조건을 추가했다. 이 조건으로 위에서 말한 첫 두 문제를 해결할 수 있다. 이 풀이에서는 s1의 첫 문자를 s2에서 찾은 다음 그 위치에서 s2를 앞뒤로 자른 다음, 뒷부분은 s1의 시작 부분과 같은지 확인하고 앞부분은 s1의 끝 부분과 같은지 확인하는 방법을 사용했다.

public static boolean isRotated(String input, String rotated) {
  if (input == null || rotated == null) {
    return false;
  } else if (input.length() != rotated.length()) {
    return false;
  } else if (Objects.equals(input, rotated)) {
    return false;
  }

  char ch = input.charAt(0);
  for (int p = rotated.indexOf(ch);
       p >= 0;
       p = rotated.indexOf(ch, p + 1)) {
    if (input.startsWith(rotated.substring(p))
        && input.endsWith(rotated.substring(0, p))) {
      return true;
    }
  }
  return false;
}

s1의 첫 문자가 s2에서 한 번만 나오라는 보장은 없으므로 s2를 잘라 순서를 바꿔 비교하는 작업을 루프를 돌며 반복해야 한다.

참고

• 2 Ways to Check if a String is Rotation of Other in Java
  첫 번째 방법은 흥미로웠지만 두 번째 방법은 제대로 동작하지 않았다.