백준 6443번 애너그램 Java

https://www.acmicpc.net/problem/6443

문제

---

생각하기

---

• 백트래킹 문제이다.

• 순서에 따른 조합을 모두 찾고, 중복을 제거해야된다.

동작

중복을 제거하기 위해 정렬 후HashSet에 저장을 했다.
또한, 입력 순서에 맞추기 위해 LinkedHashSet을 사용했다.

        for (int i = 0; i < N; i++) {
            chArr = br.readLine().toCharArray();
            Arrays.sort(chArr);
            M = chArr.length;

            StringBuilder sb2 = new StringBuilder();
            for (int j = 0; j < M; j++) {
                sb2.append(chArr[j]);
            }

            set.add(sb2.toString());
        }

        for (String str : set) {
            M = str.length();
            isVisited = new boolean[M];
            chArr = str.toCharArray();
            DFS(0, new StringBuilder(), str);
        }

결과

코드

---

Java

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

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int N, M;
    private static char[] chArr;
    private static HashSet<String> set;
    private static boolean[] isVisited;
    private static StringBuilder ans;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() throws IOException {
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < N; i++) {
            chArr = br.readLine().toCharArray();
            Arrays.sort(chArr);
            M = chArr.length;

            StringBuilder sb2 = new StringBuilder();
            for (int j = 0; j < M; j++) {
                sb2.append(chArr[j]);
            }

            set.add(sb2.toString());
        }

        for (String str : set) {
            M = str.length();
            isVisited = new boolean[M];
            chArr = str.toCharArray();
            DFS(0, new StringBuilder());
        }

        sb.append(ans.toString());
        return sb.toString();
    } // End of solve()

    private static void DFS(int depth, StringBuilder sb) {
        if (depth == M) {
            ans.append(sb).append('\n');
            return;
        }

        for (int i = 0; i < M; i++) {
            if (isVisited[i]) continue;
            if (i > 0 && chArr[i] == chArr[i - 1] && !isVisited[i - 1]) continue;

            isVisited[i] = true;
            sb.append(chArr[i]);
            DFS(depth + 1, sb);
            // 마지막 문자 다시 제거,
            sb.deleteCharAt(sb.length() - 1);
            isVisited[i] = false;
        }
    } // End of DFS()

    private static void input() throws IOException {
        N = Integer.parseInt(br.readLine());
        set = new LinkedHashSet<>();
        ans = new StringBuilder();
    } // End of input()
} // End of Main class

Kotlin

// input
private var br = System.`in`.bufferedReader()

// variables
private var N = 0
private var M = 0
private lateinit var chArr: CharArray
private lateinit var ans: StringBuilder
private lateinit var isVisited: BooleanArray


fun main() {
    val bw = System.out.bufferedWriter()

    input()

    bw.write(solve())
    bw.close()
} // End of main()

private fun solve(): String {
    val sb = StringBuilder()

    val set = LinkedHashSet<String>()
    repeat(N) {
        val temp = br.readLine().toCharArray()
        temp.sort()

        val sb2 = StringBuilder()
        temp.forEach {
            sb2.append(it)
        }

        set.add(sb2.toString())
    }

    set.forEach {
        M = it.length
        isVisited = BooleanArray(M)
        chArr = it.toCharArray()
        DFS(0, StringBuilder())
    }

    sb.append(ans)
    return sb.toString()
} // End of solve()

private fun DFS(depth: Int, sb: StringBuilder) {
    if (depth == M) {
        ans.append(sb.toString()).append('\n')
        return
    }

    for (i in 0 until M) {
        if (isVisited[i]) continue
        if (i > 0 && chArr[i] == chArr[i - 1] && !isVisited[i - 1]) continue
        
        isVisited[i] = true
        sb.append(chArr[i])
        DFS(depth + 1, sb)
        sb.deleteAt(sb.length - 1)
        isVisited[i] = false
    }
} // End of DFS()

private fun input() {
    N = br.readLine().toInt()
    ans = StringBuilder()
} // End of input()