[JAVA] 백준 6443

 

 

6443번: 애너그램

문제

씬디는 애너그램(anagram) 프로그램을 만들어 줄 수 있는 남자를 좋아한다. 참고로 씬디는 매우 예쁘다.

애너그램 프로그램이란, 입력받은 영단어의 철자들로 만들 수 있는 모든 단어를 출력하는 것이다. 가령 "abc" 를 입력받았다면, "abc", "acb", "bac", "bca", "cab", "cba" 를 출력해야 한다.

입력받은 단어내에 몇몇 철자가 중복될 수 있다. 이 경우 같은 단어가 여러 번 만들어 질 수 있는데, 한 번만 출력해야 한다. 또한 출력할 때에 알파벳 순서로 출력해야 한다.

풀이

처음에는 다음 코드처럼 백트래킹 탐색을 통해서 쉽게 모든 경우의 수를 탐색하고 출력할 수 있을 줄 알았다.

하지만 생각보다 많은 경우의 수가 존재해서 재귀의 깊이가 많이 깊어져서 문제를 해결하지 못했다.

그래서 문제에 대한 해결방법을 찾아보았고 Next Permutation Algorithm을 통해서 해결했다.!

Next Permutation Algorithm

[Algorithm] Next Permutation 알고리즘

 

📌 메모리 초과 백트래킹 코드

import java.io.*;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.stream.Collectors;

class Main {
    static boolean[] V;
    static int N;
    static char[] value;
    static StringBuilder sb = new StringBuilder();
    static LinkedList<String> disctinct = new LinkedList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int M = Integer.parseInt(br.readLine());

        for(int i=0; i<M; i++){
            value = br.readLine().toCharArray();

            Arrays.sort(value);
            N = value.length;
            V = new boolean[N];
            disctinct.clear();
            DFS(0, "");
            for(String answer : disctinct.stream().distinct().collect(Collectors.toList())){
                sb.append(answer).append("\n");
            }
        }
        System.out.println(sb);

    }

    public static void DFS(int depth, String anagram){
        if(depth == N){
            disctinct.add(anagram);
            return ;
        }

        for(int i=0; i<N; i++){

            if(!V[i]){
                V[i] = true;
                DFS(depth+1, anagram + value[i]+" ");
                V[i] = false;
            }
        }
    }
}

ㅠ.ㅠ

📌 값 입력 및 수열 찾기

int M = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
for(int i=0; i<M; i++){
    value = br.readLine().toCharArray();

    Arrays.sort(value);
    for(int j=0; j<value.length; j++){
        sb.append(value[j]);
    }
    sb.append("\n");

    while (nextPermutation(value)){
        for(int j=0; j< value.length; j++){
            sb.append(value[j]);
        }
        sb.append("\n");
    }
}
System.out.println(sb);

1. 값이 들어올 때마다 char array로 만들어서 먼저 정렬해준다. (사전 순으로 출력)
2. 정렬한 값을 첫 번째 문자열이기 때문에 결과에 담는다.
3. 리스트를 하나의 문자열로 보고 다음 문자열로 갱신하고 정답에 담아준다.

📌 nextPermutation

    public static boolean nextPermutation(char[] arr){
        int i = arr.length-1;
        int j = arr.length-1;
        // i가 i-1보다 사전순으로 더 큰 값을 가지는 문자를 찾는다.
        while(i > 0 && arr[i] <= arr[i-1]){
            i--;
        }

        if( i <= 0) return false;

        // j가 i-1보다 사전순으로 큰 값을 가지는 문자를 찾는다.
        while (arr[j] <= arr[i-1]){
            j--;
        }

        // swap
        char temp = arr[i-1];
        arr[i-1] = arr[j];
        arr[j] = temp;

        j = arr.length-1;
        while (i<j){
            temp = arr[i];
            arr[i++] = arr[j];
            arr[j--] = temp;
        }
        return true;
    }

Next Permutation 알고리즘은 다음의 절차로 해결된다.

1. 문자열의 뒤부터 탐색하면서 사전순으로 오름차순이 깨지는 부분을 찾아준다.
2. 이때 오름차순이 깨지는 인덱스가 없다면 마지막 문자열이기 때문에 false를 반환한다.
3. 다시한번 문자열의 뒤부터 탐색하면서 앞에서 오름차순이 깨지는 부분의 값보다 큰 값을 선택한다.
4. 앞에서 선택한 두 값을 swap하고 첫 번째 선택한 값 이후의 값들을 오름차순 정렬 (뒤에서 봤을때 이미 오름차순 정렬된 값들이기 때문에 reverse해줘도 된다.)해준다.

📌 전체 코드

import java.io.*;
import java.util.Arrays;

class Main {
    static char[] value;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int M = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<M; i++){
            value = br.readLine().toCharArray();

            Arrays.sort(value);
            for(int j=0; j<value.length; j++){
                sb.append(value[j]);
            }
            sb.append("\n");

            while (nextPermutation(value)){
                for(int j=0; j< value.length; j++){
                    sb.append(value[j]);
                }
                sb.append("\n");
            }
        }
        System.out.println(sb);
    }

    public static boolean nextPermutation(char[] arr){
        int i = arr.length-1;
        int j = arr.length-1;
        // i가 i-1보다 사전순으로 더 큰 값을 가지는 문자를 찾는다.
        while(i > 0 && arr[i] <= arr[i-1]){
            i--;
        }

        if( i <= 0) return false;

        // j가 i-1보다 사전순으로 큰 값을 가지는 문자를 찾는다.
        while (arr[j] <= arr[i-1]){
            j--;
        }

        // swap
        char temp = arr[i-1];
        arr[i-1] = arr[j];
        arr[j] = temp;

        j = arr.length-1;
        while (i<j){
            temp = arr[i];
            arr[i++] = arr[j];
            arr[j--] = temp;
        }
        return true;
    }

}

결과