[C#] 백준 15663번 문제풀이

문제번호: 15663

문제명: N과 M (9)

문제링크: https://www.acmicpc.net/problem/15663

문제내용과 예제 입/출력은 위 문제 링크에서 확인해 주시기 바랍니다

오늘도 N과M 시리즈 문제를 풀었습니다. 이번에 푼 문제는 9번 문제입니다. 중복된 수열을 출력하지 말라는 조건이 추가되었습니다. 따라서 저는 Recur함수 안에 사용된 수를 저장하는 변수를 선언하여 중복된 수열이 만들어지지 않도록 방지했습니다.
다음은 정답코드입니다.

 

public static void Main()
{
    StreamReader sr = new StreamReader(Console.OpenStandardInput());
    StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

    int[] NM = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
    List<int> Numbers = Array.ConvertAll(sr.ReadLine().Split(), int.Parse).ToList();
    Numbers.Sort();
    int N = NM[0]; // 3
    int M = NM[1]; // 1

    Stack<int> rs = new Stack<int>();
    bool[] chk = new bool[N + 1]; // 4

    Recur(0);

    void Recur(int num)
    {
        if (num == M)
        {
            //Console.WriteLine(rs.ToString());
            foreach (int a in rs.Reverse())
            {
                sw.Write(a + " ");
            }
            sw.WriteLine();
            return;
        }

        int pastNum = -1;

        for (int i = 1; i < N + 1; i++)
        {
            int number = Numbers[i - 1];
            if (chk[i] == false)
            {
                if (pastNum == number) continue;

                pastNum = number;
                chk[i] = true;
                rs.Push(number);
                Recur(num + 1);
                chk[i] = false;
                if (rs.Count > 0)
                    rs.Pop();
            }
        }
    }

    sr.Close();
    sw.Close();
}