CS 공부 & 면접 맛보기 0x06 [자료구조] : 자바(Java)에서 문자열을 뒤집는 방법

2025. 1. 6. 23:00코딩 도구/CS 면접 도구

반응형

자바(Java)에서 문자열을 뒤집는 방법: 재귀적 접근


질문

자바에서 문자열을 뒤집는 방법은 무엇인가요?


답변

자바에서 문자열을 뒤집는 방법 중 하나는 재귀(Recursion)를 사용하는 것입니다.
재귀를 사용하면 문자열을 작은 단위로 나누어 처리하고, 나머지 문자열을 다시 호출하는 방식으로 뒤집을 수 있습니다.


질문과 답변에 대한 설명

재귀(Recursion)란?

재귀는 함수가 자기 자신을 호출하는 프로그래밍 기법입니다.

  • 기본 조건(Base Case): 재귀가 종료되는 조건을 정의.
  • 재귀 호출(Recursive Case): 함수를 반복적으로 호출.

자바에서 문자열을 재귀적으로 뒤집는 원리

아이디어:

  1. 문자열의 첫 번째 문자와 나머지 문자를 분리.
  2. 나머지 문자열을 재귀적으로 뒤집음.
  3. 마지막에 첫 번째 문자를 다시 추가하여 문자열을 완성.

자바 코드 예시 (재귀적 문자열 뒤집기)

public class ReverseString {

    // 재귀적으로 문자열을 뒤집는 메서드
    public static String reverseRecursive(String str) {
        // 기본 조건: 문자열이 비어있거나 길이가 1일 경우
        if (str == null || str.length() <= 1) {
            return str;
        }
        // 첫 글자를 뒤로 보내고, 나머지 문자열을 재귀적으로 뒤집기
        return reverseRecursive(str.substring(1)) + str.charAt(0);
    }

    public static void main(String[] args) {
        String input = "hello";
        String reversed = reverseRecursive(input);
        System.out.println("원래 문자열: " + input);
        System.out.println("뒤집힌 문자열: " + reversed);
    }
}

 


코드 동작 과정 (문자열 "hello" 기준)

  1. reverseRecursive("hello") → "ello" + h
  2. reverseRecursive("ello") → "llo" + e
  3. reverseRecursive("llo") → "lo" + l
  4. reverseRecursive("lo") → "o" + l
  5. reverseRecursive("o") → "o" (기본 조건 도달)

결과: "olleh"

시간 및 공간 복잡도

  • 시간 복잡도: O(n) (n은 문자열의 길이, 한 번의 순회로 모든 문자를 뒤집음)
  • 공간 복잡도: O(n) (재귀 호출 스택의 깊이가 문자열 길이와 동일)

비재귀적(반복문) 방식과 비교

재귀적 방식 외에도 반복문을 사용하여 문자열을 뒤집을 수 있습니다.

public class ReverseStringIterative {

    public static String reverseIterative(String str) {
        StringBuilder reversed = new StringBuilder();
        for (int i = str.length() - 1; i >= 0; i--) {
            reversed.append(str.charAt(i));
        }
        return reversed.toString();
    }

    public static void main(String[] args) {
        String input = "hello";
        System.out.println("뒤집힌 문자열: " + reverseIterative(input));
    }
}

재귀적 vs 반복적 방식 비교표

구분재귀적 방법반복문 방법

코드 가독성 간결하지만 이해하기 어려울 수 있음 직관적이고 이해하기 쉬움
시간 복잡도 O(n) O(n)
공간 복잡도 O(n) (재귀 스택 사용) O(1) (반복문만 사용)
실행 속도 느림 (재귀 호출 오버헤드) 빠름 (반복문은 오버헤드 없음)
적합한 경우 알고리즘 학습, 개념 이해에 적합 대용량 데이터 및 실무에서 적합

면접 시 고려할 수 있는 추가 질문 포인트

  1. 재귀 호출의 장점과 단점은 무엇인가요?
    • 장점: 코드가 간결하고 수학적 문제 해결에 적합.
    • 단점: 메모리 사용량이 많고, 스택 오버플로우 가능성 존재.
  2. 재귀 호출의 종료 조건을 설정하는 이유는?
    • 종료 조건이 없으면 무한 재귀에 빠져 StackOverflowError 발생.
  3. 문자열을 뒤집는 다른 방법은 무엇이 있나요?
    • StringBuilder의 reverse() 메서드 사용.
    • 투 포인터 알고리즘 사용.
반응형