Java로 문자열의 중복 없는 고유 순열 출력하기

문자열의 고유한(distinct) 순열, 즉 중복을 제거한 모든 순열을 출력하는 Java 프로그램은 다음과 같습니다.

예제 코드

import java.util.ArrayList;
public class Demo{
    static boolean is_present(String my_str, ArrayList<String> rem){
        for (String str : rem){
            if (str.equals(my_str))
            return true;
        }
        return false;
    }
    static ArrayList<String> distinct_pattern(String str){
        if (str.length() == 0){
            ArrayList<String> base_Val = new ArrayList<>();
            base_Val.add("");
            return base_Val;
        }
        char ch = str.charAt(0);
        String rem_str = str.substring(1);
        ArrayList<String> prev_str = distinct_pattern(rem_str);
        ArrayList<String> rem = new ArrayList<>();
        for (String my_str : prev_str){
            for (int i = 0; i <= my_str.length(); i++){
                String f = my_str.substring(0, i) + ch + my_str.substring(i);
                if (!is_present(f, rem))
                rem.add(f);
            }
        }
        return rem;
    }
    public static void main(String[] args){
        String my_str = "mnqm";
        System.out.println("The distinct permutations of the string are ");
        System.out.println(distinct_pattern(my_str));
    }
}

실행 결과

The distinct permutations of the string are
[mnqm, nmqm, nqmm, mqnm, qmnm, qnmm, mqmn, qmmn, mnmq, nmmq, mmnq, mmqn]

코드 동작 원리

Demo라는 이름의 클래스에는 is_present라는 Boolean 타입의 함수가 포함되어 있습니다. 이 함수는 특정 문자열이 이미 결과 목록(ArrayList)에 존재하는지 확인하며, 존재하면 true, 존재하지 않으면 false를 반환합니다. 이를 통해 중복된 순열이 결과에 추가되는 것을 사전에 차단합니다.

핵심 역할을 하는 또 다른 함수 distinct_pattern은 순열을 저장할 ArrayList를 생성하며, 재귀(recursion) 방식으로 동작합니다. 먼저 문자열의 첫 번째 문자를 분리하고, 나머지 부분을 rem_str이라는 별도의 문자열 변수에 저장합니다. 그런 다음 이 rem_str을 인자로 전달하여 distinct_pattern 함수를 재귀적으로 호출합니다.

재귀 호출의 결과로 얻어진 기존 순열들에 대해, 분리해 둔 문자를 삽입할 수 있는 모든 위치(0부터 문자열 길이까지)를 하나씩 검사하면서 새로운 순열을 만듭니다. 이때 is_present 함수로 중복 여부를 확인한 뒤, 기존에 없던 순열만 결과 목록에 추가합니다. 이러한 과정 덕분에 같은 문자가 반복되어 나타나는 입력(예: "mnqm"의 경우 'm'이 두 번 등장)에서도 중복 없는 고유한 순열만 남게 됩니다.

마지막으로 main 함수에서 대상 문자열("mnqm")을 정의하고, 이 문자열에 대해 distinct_pattern 함수를 호출합니다. 함수가 반환한 모든 고유 순열이 콘솔에 출력되며, 위 실행 결과에서 확인할 수 있듯이 총 12개의 서로 다른 순열이 생성됩니다.

참고: 성능 개선 팁

위 코드는 매번 is_present 함수로 선형 탐색을 수행하므로, 문자열이 길어질수록 시간 복잡도가 빠르게 증가할 수 있습니다. 중복 검사가 필요한 경우 ArrayList 대신 HashSet을 사용하면 해시 기반 조회(O(1))로 성능을 크게 향상시킬 수 있습니다.