[백준 6443] 애너그램 (C#, C++) - soo:bak

문제 링크

6443번 - 애너그램

설명

주어진 단어로 만들 수 있는 모든 애너그램을 사전순으로 출력하는 문제입니다.

입력으로 주어지는 각 단어는 소문자로만 구성되며,

출력할 때는 가능한 모든 문자 조합 중 사전순으로 정렬된 중복 없는 결과만 출력해야 합니다.

입력의 각 테스트케이스마다 다음 조건을 만족하는 모든 조합을 출력해야 합니다:

• 문자열의 알파벳을 모두 사용하여 만들 수 있는 모든 순열
• 중복 문자로 인해 생기는 중복 순열은 한 번만 출력
• 출력은 반드시 사전순이어야 함

---

접근법

이 문제는 순열(permutaion)을 기반으로 다음과 같이 풀이합니다:

• 먼저 주어진 문자열을 정렬하여 가장 작은 사전순 조합으로 시작합니다.
• 이후 다음 사전순 순열을 반복적으로 생성하면서 출력합니다.

사전순 순열 생성 알고리듬은 다음과 같은 흐름으로 진행됩니다:

1. 뒤에서부터 첫 번째로 증가하지 않는 인덱스를 찾습니다.
2. 해당 인덱스보다 뒤에서 처음으로 큰 값을 찾아 교환합니다.
3. 교환한 이후의 모든 값을 오름차순으로 정렬(또는 뒤집기)합니다.

이 과정을 통해 중복 없이 모든 순열을 사전순으로 생성할 수 있습니다.

---

Code

C#

using System;
using System.Linq;
using System.Text;

class Program {
  static void Main() {
    int t = int.Parse(Console.ReadLine());
    var sb = new StringBuilder();

    while (t-- > 0) {
      var s = Console.ReadLine().ToCharArray();
      Array.Sort(s);
      sb.AppendLine(new string(s));

      while (true) {
        int i = s.Length - 2;
        while (i >= 0 && s[i] >= s[i + 1])
          i--;

        if (i < 0)
          break;

        int j = s.Length - 1;
        while (s[j] <= s[i])
          j--;

        (s[i], s[j]) = (s[j], s[i]);
        Array.Reverse(s, i + 1, s.Length - i - 1);
        sb.AppendLine(new string(s));
      }
    }

    Console.Write(sb.ToString());
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int t; cin >> t;
  while (t--) {
    string s; cin >> s;

    sort(s.begin(), s.end());
    cout << s << "\n";

    while (true) {
      int i = s.size() - 2;
      while (i >= 0 && s[i] >= s[i + 1])
        --i;

      if (i < 0) break;

      int j = s.size() - 1;
      while (s[j] <= s[i])
        --j;

      swap(s[i], s[j]);
      reverse(s.begin() + i + 1, s.end());

      cout << s << "\n";
    }
  }

  return 0;
}