Java ArrayList를 활용해 문자열의 모든 순열 출력하기

이 글에서는 길이가 n인 문자열이 주어졌을 때, 해당 문자열의 모든 순열(permutation)을 출력하는 방법을 다룹니다. 특히 이번 튜토리얼에서는 일반적인 배열 대신 ArrayList를 활용하여 순열을 생성하고 출력하는 방법을 소개합니다.

문제 이해하기

먼저 예시를 통해 문제를 살펴보겠습니다.

입력 − string = 'XYZ'

출력 − XYZ, XZY, YXZ, YZX, ZXY, ZYX

길이가 3인 문자열은 3! = 6개의 순열을 가질 수 있습니다. 즉, 문자열의 각 문자를 서로 다른 순서로 배치한 모든 경우의 수를 구하는 것이 목표입니다.

해결 접근 방식

이 문제는 재귀 함수를 사용하여 해결할 수 있으며, 결과값은 ArrayList 형태로 반환됩니다. 알고리즘의 핵심 흐름은 다음과 같습니다.

문자열의 첫 번째 문자를 분리합니다.
나머지 부분 문자열에 대해 재귀적으로 순열을 생성합니다.
분리했던 문자를 기존 순열의 가능한 모든 위치(앞, 중간, 뒤)에 삽입하여 새로운 순열을 만듭니다.
기저 조건(base case)은 빈 문자열일 때이며, 이때는 빈 문자열 하나를 담은 리스트를 반환합니다.

구현 예제

다음은 위 알고리즘을 ArrayList로 구현한 자바 코드입니다.

import java.util.ArrayList;
public class Main{
    static void printArrayList(ArrayList<String> combo) {
        combo.remove("");
        for (int i = 0; i < combo.size(); i++)
        System.out.print(combo.get(i)+"\t");
    }
    public static ArrayList<String> generatePermutation(String str) {
        if (str.length() == 0) {
            ArrayList<String> empty = new ArrayList<>();
            empty.add("");
            return empty;
        }
        char ch = str.charAt(0);
        String subStr = str.substring(1);
        ArrayList<String> lastCombination = generatePermutation(subStr);
        ArrayList<String> newCombination = new ArrayList<>();
        for (String val : lastCombination) {
            for (int i = 0; i <= val.length(); i++) {
                newCombination.add(val.substring(0, i) + ch + val.substring(i));
            }
        }
        return newCombination;
    }
    public static void main(String[] args) {
        String str = "NOPQ";
        System.out.println("Permutations of string are :");
        printArrayList(generatePermutation(str));
    }
}

실행 결과

Permutations of string are :
NOPQ ONPQ OPNQ OPQN NPOQ PNOQ
PONQ POQN NPQO PNQO PQNO
PQON NOQP ONQP OQNP OQPN
NQOP QNOP QONP QOPN NQPO
QNPO QPNO QPON

코드 동작 원리

generatePermutation() 메서드는 재귀 호출을 통해 동작합니다. 문자열 "NOPQ"가 입력되면 다음 과정이 진행됩니다.

첫 문자 'N'을 분리하고, 나머지 "OPQ"에 대한 순열을 재귀적으로 구합니다.
"OPQ" 역시 같은 방식으로 처리되어 최종적으로 빈 문자열에 도달하면, 거꾸로 올라가면서 각 단계마다 분리했던 문자를 기존 순열의 모든 위치에 삽입합니다.
내부 반복문 for (int i = 0; i <= val.length(); i++)는 앞, 중간, 뒤 등 모든 삽입 지점을 처리하는 역할을 합니다.
길이가 n인 문자열의 순열 개수는 n!이므로, 이 알고리즘의 시간 복잡도는 O(n × n!)입니다.

이처럼 재귀와 ArrayList를 조합하면 문자열의 모든 순열을 깔끔하게 생성하고 출력할 수 있습니다.