Jwhy

Jwhy

끊임없이 고민하는 개발자

[백준][JAVA] - 애너그램(6443)

문제 소개

🥇️ 문제 레벨 : 골드5

🔔 문제 유형 : 백트래킹, 문자열

💬 풀이 언어 : JAVA

⏱️ 풀이 시간 : 20분

🖇️ 문제 링크 : 백준 문제 링크

📝 문제

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

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

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

🤔 문제 분석

N과 M을 열심히 풀었다면 쉽게 풀이할 수 있는 문제이다.

문제에서 주어진 예시와 같이 주어진 문자열로 만들 수 있는 모든 조합을 구하면 된다.

단, 가장 주의해야할 점은 중복된 문자가 주어졌을 때, 일반적인 방식으로 풀이할 경우 결과값이 중복될 수 있다.

예를 들어보면 아래와 같다.

  1. 문자열로 acba가 주어진다.
  2. 문자열을 정렬해 문자 배열로 저장한다.
  3. [a, a, b, c]가 된다.

첫 자리를 0번 인덱스 부터 시작하면, 아래와 같은 결과가 나온다.

aabc
aacb
abac
abca
acab
acba

다음으로 첫 자리를 1번 인덱스로 시작하면 위와 같은 결과가 나온다. 즉, 출력값이 중복된다는 것이다. 그렇기 때문에 값을 메모제이션해 동일한 값이 나오지 않도록하는 방식으로 풀이하면 된다.

😎 최종 코드

메모리 : 13508 KB
시간 : 200 ms

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Main {
    static BufferedWriter bw;
    static int N, length;
    static char[] alphas, ana, max;
    static boolean[] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());

        for (int i = 0; i < N; i++) {
            alphas = br.readLine().toCharArray();
            length = alphas.length;

            visited = new boolean[length];
            max = new char[length];
            ana = new char[length];

            Arrays.sort(alphas);
            backTracking(0);
        }

        bw.flush();
        br.close();
        bw.close();
    }

    private static void backTracking(int depth) throws IOException {
        if (depth == length) {
            bw.write(ana);
            bw.write('\n');
            return;
        }

        max[depth] = 0;
        for (int i = 0; i < length; i++) {
            if(mx[depth] >= alphas[i]) continue;
            if (!visited[i]) {
                visited[i] = true;
                max[depth] = ana[depth] = alphas[i];
                backTracking(depth + 1);
                visited[i] = false;
            }
        }
    }
}

댓글남기기

참고