[Algorithm/Java] 백준 6443번 - 에너그램

---

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

---

🔍 문제 풀이

문제 도식화

알게된 점

char[]는 println이 문자열 취급해주니 그대로 찍어도 된다

시간 초과 원인: for(char c: ans) System.out.print(c);

• 문자를 하나씩 찍어서 I/O 호출 과다
• 그냥 문자를 System.out.println(ans); 사용하여 출력
  • PrintStream.println(char[] x) 오버로드가 배열을 문자열처럼 바로 출력해 준다고 한다.
• char[]만 특별히 문자열로 변환하여 출력해줌
• 다른 타입은 주소값만 출력됨

ㅠㅠ

중복 순열 제거 조건

if (j > 0 && arr[j] == arr[j - 1] && !v[j - 1]) continue;

• arr[j] == arr[j - 1]
  • 바로 앞 원소와 현재 원소가 같은 문자임을 확인
  • 같은 문자 그룹 안에서 중복 방지를 위한 조건
• !v[j - 1]
  • 앞의 같은 문자를 아직 사용하지 않았다면 이번것도 건너뜀
  • 항상 같은 문자 중에서 왼쪽 것부터 먼저 사용해야 순서가 한 번만 만들어지기 때문

💻 코드

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

public class Main {
    static char[] arr;
    static boolean[] v;
    static char[] ans;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        while(n --> 0) {
            arr = br.readLine().toCharArray();
            v = new boolean[arr.length];
            ans = new char[arr.length];

            Arrays.sort(arr);

            dfs(0);
        }
    }

    static void dfs(int depth) {
        // 1. 종료 조건
        if (depth == arr.length) {
            System.out.println(ans);
            return;
        }

        // 2. dfs 호출
        for (int j = 0; j < arr.length; j++) {
            // 중복 순열 제거
            if (j > 0 && arr[j-1] == arr[j] && !v[j-1]) continue;

            if(!v[j]){
                v[j] = true;

                ans[depth] = arr[j];
                dfs(depth + 1);

                v[j] = false;
            }

        }

    }
}