이 글에서는 자바(Java)를 사용해 문자열의 모든 부분집합, 즉 부분 문자열(substring)을 찾는 방법을 알아봅니다. 여기서 문자열(String)은 하나 이상의 문자가 큰따옴표(“ ”)로 묶여 있는 자료형을 의미하며, 문자열의 일부 또는 부분집합을 '부분 문자열'이라고 부릅니다.
참고로 길이가 n인 문자열은 최대 n × (n + 1) / 2개의 부분 문자열을 가질 수 있습니다. 아래는 실제 동작 예시입니다.
입력 및 출력 예시
입력
정의된 문자열: JVM
출력
문자열의 부분집합: J JV JVM V VM M
알고리즘
1단계 - 시작합니다. 2단계 - 필요한 변수들을 선언합니다. 3단계 - 값을 정의합니다. 4단계 - 매 반복마다 증가시킬 임시 변수(temp)를 초기화합니다. 5단계 - 두 개의 중첩 루프(for문)를 사용해 문자열의 길이만큼 순회합니다. 6단계 - 지정한 범위의 부분 문자열을 추출하고, 매 반복마다 임시 변수를 1씩 증가시킵니다. 7단계 - 루프를 사용해 저장된 모든 부분 문자열을 출력합니다. 8단계 - 종료합니다.
예제 1: main 메서드 안에서 처리하기
첫 번째 예제는 모든 연산을 하나의 'main' 함수 안에 직접 작성한 방식입니다.
public class Demo {
public static void main(String[] args) {
String input_string = "JVM";
int string_length = input_string.length();
int temp = 0;
System.out.println("정의된 문자열: " + input_string);
String string_array[] = new String[string_length * (string_length + 1) / 2];
for(int i = 0; i < string_length; i++) {
for(int j = i; j < string_length; j++) {
string_array[temp] = input_string.substring(i, j + 1);
temp++;
}
}
System.out.println("문자열의 부분집합:");
for(int i = 0; i < string_array.length; i++) {
System.out.println(string_array[i]);
}
}
}
출력 결과
정의된 문자열: JVM 문자열의 부분집합: J JV JVM V VM M
코드 설명
- 바깥쪽 루프(i)는 부분 문자열의 시작 인덱스를 결정하고, 안쪽 루프(j)는 끝 인덱스를 결정합니다.
- substring(i, j + 1) 메서드를 호출하면 시작 위치부터 끝 위치까지의 문자열이 잘려 나옵니다.
- 배열 크기를 n × (n + 1) / 2로 선언하는 이유는, 이것이 길이가 n인 문자열이 가질 수 있는 부분 문자열의 총 개수와 정확히 일치하기 때문입니다.
예제 2: 별도의 메서드로 분리하기 (객체지향 방식)
두 번째 예제는 연산 로직을 별도의 메서드로 캡슐화하여 객체지향 프로그래밍(OOP) 스타일로 작성한 것입니다. 재사용성과 가독성 면에서 더 유리합니다.
public class Demo {
static void subsets(String input_string){
int string_length = input_string.length();
int temp = 0;
String string_array[] = new String[string_length * (string_length + 1) / 2];
for(int i = 0; i < string_length; i++) {
for(int j = i; j < string_length; j++) {
string_array[temp] = input_string.substring(i, j + 1);
temp++;
}
}
System.out.println("문자열의 부분집합:");
for(int i = 0; i < string_array.length; i++) {
System.out.println(string_array[i]);
}
}
public static void main(String[] args) {
String input_string = "JVM";
System.out.println("정의된 문자열: " + input_string);
subsets(input_string);
}
}
출력 결과
정의된 문자열: JVM 문자열의 부분집합: J JV JVM V VM M
마무리
이처럼 두 개의 중첩 루프와 substring() 메서드만 활용하면 문자열의 모든 부분 문자열을 손쉽게 구할 수 있습니다. 두 예제 모두 결과는 동일하지만, 로직을 메서드로 분리한 예제 2가 코드 관리와 재사용 측면에서 더 권장되는 방식입니다. 이 알고리즘의 시간 복잡도는 O(n²)입니다.