[알고리즘 문제 풀기] N과 M (12)(15666)

1. 문제 풀이 아이디어

• 주어진 수열에서 중복을 제거하고 정렬한 후, 오름차순 순열을 백트래킹으로 생성해 문제를 해결한다.

2. 나의 정답 코드

using System.Text;
StringBuilder sb = new StringBuilder("");

using (StreamReader sr = new StreamReader(Console.OpenStandardInput()))
using (StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()))
{
    string[] split = sr.ReadLine().Split();
    int n = int.Parse(split[0]);
    int m = int.Parse(split[1]);

    SortedSet<int> set = new SortedSet<int>();
    split = sr.ReadLine().Split();
    for (int i = 0; i < n; i++)
    {
        set.Add(int.Parse(split[i]));
    }
    int[] a = set.ToArray();

    int[] result = new int[m];
    solve(0);
    sw.Write(sb);

    void solve(int t)
    {
        if (t == m)
        {
            sb.AppendLine(string.Join(" ", result));
            return;
        }
        for (int i = 0; i < a.Length; i++)
        {
            if (t > 0 && result[t - 1] > a[i]) continue;
            result[t] = a[i];
            solve(t + 1);
        }
    }
}

3. 정리

• SortedSet<int>을 사용하여 중복을 제거하고 자동 정렬된 배열 a를 생성한다.

• 백트래킹을 통해 m개의 수를 선택하며, 오름차순이 유지되도록 이전에 선택한 값보다 작은 값은 선택하지 않는다.

• solve(t) 함수에서 t == m이면 현재 순열을 출력하고, 그렇지 않으면 가능한 모든 값을 선택하여 재귀적으로 호출한다.