DSPL: 문자열 Reverse 시키기

---

Goldman Sachs Interview Question: Level(Easy)

주어진 문자열을 역순시키는 프로그램을 작성하시오. 

Built-in 메서드는 사용할 수 없으며, 문자열의 길이가 충분히 긴 경우에도 효율적인 시간에 수행되도록 작성하시오. 

시간 복잡도를 계산하시오.

---

가장 먼저 떠오르는 아이디어는 문자열의 처음과 끝 문자를 각각 교환(swap)하는 방식으로 역순화하면 되겠다. 이 경우 문자열의 길이가 n이라면 n/2번의 반복이 필요하므로, O(n) 복잡도를 가진다. 비교적 쉬운 난이도의 문제다.

구현시 고려할 점은 Java에서 문자열 객체는 immutable이므로 StringBuffer나 char 배열로 변환하여 처리해야겠다.

public class ReverseStringTest {

 public static String reverseString(String string) {
  StringBuffer strBuffer = new StringBuffer(string);

  for(int i=0; i<strBuffer.length()/2; i++) {
   char tmpChar = strBuffer.charAt(i);
   strBuffer.setCharAt(i, strBuffer.charAt(strBuffer.length()-i-1));
   strBuffer.setCharAt(strBuffer.length()-i-1, tmpChar);
  }

  return strBuffer.toString();
 }

 public static String generateRandomString(int length) {
  StringBuffer tmpStr = new StringBuffer();

  for(int i=0; i<length; i++) {
   tmpStr.append(generateRandomChar());
  }

  return tmpStr.toString();
 }

 private static char generateRandomChar() {
  final String charSet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
  int index = new Random().nextInt(charSet.length());
  return charSet.charAt(index);
 }

 public static void main(String[] args) {
  System.out.println(reverseString("A"));
  System.out.println(reverseString("AB"));
  System.out.println(reverseString("ABA"));
  System.out.println(reverseString("ACBC"));

  String randomString = generateRandomString(1000);
  System.out.println(randomString);
  System.out.println(reverseString(randomString));
  
  System.out.println("> done");
  System.exit(0);
 }

}

기타 구현 방법

A. 입력 문자열의 마지막 문자를 시작문자로 하는 새로운 문자열을 구성하는 방법이 있겠다. 아래 샘플코드는 StringBuffer 대신 char 배열을 이용했다.

public static String reverseString2(String string) {

    char[] charArray = new char[string.length()];

    for(int i=0; i<charArray.length; i++)
        charArray[i] = string.charAt(string.length()-i-1);
    
    return new String(charArray);
}

B. 재귀적인 방법으로 구현한다면 다음과 같이 할 수도 있겠다.

public static String reverseStringRec(String string) {
    return reverseRec(new StringBuffer(string), 0, string.length()-1).toString();
}
//helper method
private static StringBuffer reverseRec(StringBuffer sb, int left, int right) {
    if( Math.abs(left-right) < 2 ) {
        return sb;
    } else {
        char tmpChar = sb.charAt(left);
        sb.setCharAt(left, sb.charAt(right));
        sb.setCharAt(right, tmpChar);
        return reverseRec(sb, left+1, right-1);
    }
}

C. 마지막으로 StringBuffer 클래스의 reverse() 메서드를 활용하는 방법이다.

public static String reverseStringAPI(String string) {
    return new StringBuffer(string).reverse().toString();
}

[참고문헌]
1. Programming Interview Questions: CareerCup.com

Loading ...