CS 공부 & 면접 맛보기 0x06 [자료구조] : 자바(Java)에서 문자열을 뒤집는 방법
2025. 1. 6. 23:00ㆍ코딩 도구/CS 면접 도구
반응형
자바(Java)에서 문자열을 뒤집는 방법: 재귀적 접근
질문
자바에서 문자열을 뒤집는 방법은 무엇인가요?
답변
자바에서 문자열을 뒤집는 방법 중 하나는 재귀(Recursion)를 사용하는 것입니다.
재귀를 사용하면 문자열을 작은 단위로 나누어 처리하고, 나머지 문자열을 다시 호출하는 방식으로 뒤집을 수 있습니다.
질문과 답변에 대한 설명
재귀(Recursion)란?
재귀는 함수가 자기 자신을 호출하는 프로그래밍 기법입니다.
- 기본 조건(Base Case): 재귀가 종료되는 조건을 정의.
- 재귀 호출(Recursive Case): 함수를 반복적으로 호출.
자바에서 문자열을 재귀적으로 뒤집는 원리
아이디어:
- 문자열의 첫 번째 문자와 나머지 문자를 분리.
- 나머지 문자열을 재귀적으로 뒤집음.
- 마지막에 첫 번째 문자를 다시 추가하여 문자열을 완성.
자바 코드 예시 (재귀적 문자열 뒤집기)
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" 기준)
- reverseRecursive("hello") → "ello" + h
- reverseRecursive("ello") → "llo" + e
- reverseRecursive("llo") → "lo" + l
- reverseRecursive("lo") → "o" + l
- 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) (반복문만 사용) |
실행 속도 | 느림 (재귀 호출 오버헤드) | 빠름 (반복문은 오버헤드 없음) |
적합한 경우 | 알고리즘 학습, 개념 이해에 적합 | 대용량 데이터 및 실무에서 적합 |
면접 시 고려할 수 있는 추가 질문 포인트
- 재귀 호출의 장점과 단점은 무엇인가요?
- 장점: 코드가 간결하고 수학적 문제 해결에 적합.
- 단점: 메모리 사용량이 많고, 스택 오버플로우 가능성 존재.
- 재귀 호출의 종료 조건을 설정하는 이유는?
- 종료 조건이 없으면 무한 재귀에 빠져 StackOverflowError 발생.
- 문자열을 뒤집는 다른 방법은 무엇이 있나요?
- StringBuilder의 reverse() 메서드 사용.
- 투 포인터 알고리즘 사용.
반응형
'코딩 도구 > CS 면접 도구' 카테고리의 다른 글
CS 공부 & 면접 맛보기 0x08 [자료구조] : 그래프와 트리의 차이점 (0) | 2025.01.08 |
---|---|
CS 공부 & 면접 맛보기 0x07 [자료구조] : 이진 탐색 트리(Binary Search Tree, BST) 설명 (0) | 2025.01.07 |
CS 공부 & 면접 맛보기 0x05 [자료구조] : 배열에서 중복된 정수 찾기 (0) | 2025.01.05 |
CS 공부 & 면접 맛보기 0x04 [자료구조] : 원형 연결 리스트를 확인하는 방법 (1) | 2025.01.04 |
CS 공부 & 면접 맛보기 0x03 [자료구조] :연결 리스트에서 중간값을 찾는 효율적인 방법 (2) | 2025.01.03 |