6443번 - 애너그램

1️⃣ Next Permutation

 

✏️ 풀이 과정

순열을 만드는 방법에는 방문여부 표시(or 비트마스킹)로 만드는 방법, 인덱스의 적절한 교환(swap)으로 만드는 방법, 그리고 Next Permutation으로 만드는 방법이 있는데 이 문제의 경우 중복을 포함하는데다 사전순으로 출력해야하기 때문에 넥스트 퍼뮤테이션을 사용하는 것이 가장 간단한 방법입니다.(직접 부딪혀본 결과 방문표시는 중복 제거에, 교환은 사전순 출력에 애로사항이 있었습니다. 방법이 없지는 않겠지만은...)

 

넥스트 퍼뮤테이션은 주어진 배열에서 사전 순으로 바로 다음 순서가 어떻게 될지 찾는 알고리즘입니다. 이 과정은 크게 두 부분으로 나누어지는데 하나는 가장 뒤에서부터 값이 어디까지 증가하는지 판단해서 내려가기 바로 직전의 꼭대기 지점을 찾아냅니다.(그런 지점이 존재하지 않을 경우 내림차순으로 정렬된 것이므로 마지막 순서에 해당됩니다. 시작은 오름차순이므로) 그 다음 단계는 다시 가장 뒤에서부터 이 꼭대기 바로 다음의 꺾인 지점에 해당하는 원소와 교체할 더 큰 원소를 찾는 것입니다.(현재 탐색한 꺾이기 전의 오른쪽 부분은 내림차순으로 정렬되어 있어서 앞자리가 더 커져야 다음 순서가 되기 때문에) 교체를 완료했다면 꼭대기 지점과 맨 끝에서 서로 한칸씩 내려오면서 각각 맞바꿔주면 다시 오름차순으로 정렬되고 알고리즘이 끝납니다. 이 결과가 다음 순열에 해당합니다. 이후 또 실행하게 되면 맨 끝자리부터 다시 바꿔나가게 됩니다. (오름차순으로 정렬되었기 때문에 같은 알고리즘을 적용하면 끝자리부터 바뀌게 될 것을 예측할 수 있습니다.)

 

넥스트 퍼뮤테이션 메서드를 구현했다면 while문을 통해 순열이 내림차순으로 정렬될 때까지(false 리턴 시) 계속해서 메서드를 실행해주면 모든 순열의 경우의 수를 얻을 수 있습니다. 문제에서는 이를 배열(자바일 경우 StringBuilder)에 저장했다가 한 번에 출력했습니다.  

 

⏱ 시간 복잡도

Next Permutation을 비롯한 순열 생성 알고리즘은 O(N!)의 시간 복잡도를 갖고 있습니다. 단어의 길이가 최대 20이므로 20! = 2432902008176640000... 까지 가능하다고 볼 수 있으나 문제 조건 상 실제로는 애너그램의 수(다음 순열의 수)가 100000개 이하이기 때문에 알고리즘 특성상 100000 * 20(+a), 대략 200만번가량의 계산으로 문제를 해결할 수 있습니다. N이 몇까지 가능한 지는 나와있지 않지만 100개 안쪽으로만 들어오면 충분히 시간 내에 해결될 것을 예상할 수 있습니다.  

 

💻 코드

JavaScript

const input = require("fs")
    .readFileSync(process.platform === "linux" ? "/dev/stdin" : "input.txt")
    .toString()
    .trim()
    .split("\n");

const N = Number(input[0]);
const result = [];

const np = (str) => {
    let N = str.length;
    let i = N - 1;
    while (i > 0 && str[i - 1] >= str[i]) i--;

    if (i == 0) return false;

    let j = N - 1;
    while (str[i - 1] >= str[j]) j--;

    [str[i - 1], str[j]] = [str[j], str[i - 1]];

    let k = N - 1;
    while (i < k) {
        [str[i], str[k]] = [str[k], str[i]];
        i++;
        k--;
    }

    return true;
};

for (let i = 1; i <= N; i++) {
    let str = [...input[i]].sort();
    do {
        result.push(str.join(""));
    } while (np(str));
}

console.log(result.join("\n"));