[백준] 15666 - N과 M (12)

1. 문제

15666번: N과 M (12)

2. 개요

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• N개의 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.

3. 풀이 및 코드

3-1. 풀이

백트래킹으로 조건을 만족하는 수열을 찾은 뒤 중복되지 않게 출력한다.

3-2. Python

import sys

N, M = map(int, sys.stdin.readline().split())

nums = sorted(list(map(int, sys.stdin.readline().split())))

results = set()

def bt(idx = 0, cnt = 0, l = []):
    if cnt == M:
        results.add(tuple(l))

    else:
        for i in range(idx, N):
            bt(i, cnt + 1, l + [nums[i]])

bt()

for result in sorted(list(results)):
    print(*result)

3-3. C#

C#의 경우.. distinct나 HashSet을 이용하여 중복을 제거하는 게 일반적인 것 같은데,

배열이나 리스트의 경우 내용은 동일해도 참조값(주소) 이 다르면 이를 중복으로 인식하지 못해 중복값을 처리하지 못했다. 그래서 string형식으로 바꿔 해결했다.

namespace boj_15666
{
    internal class Program
    {
        static string[] input;
        static int N;
        static int M;
        static int[] nums;
        static HashSet<string> results;
        static void Main(string[] args)
        {
            input = Console.ReadLine().Split();
            N = int.Parse(input[0]);
            M = int.Parse(input[1]);

            nums = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            Array.Sort(nums);

            results = new HashSet<string>();
            BT(0, 0, "");

            foreach (string result in results)
            {
                Console.WriteLine(result);
            }
        }

        static void BT(int idx, int cnt, string s)
        {
            if (cnt == M)
            {
                results.Add(s);
            }
                

            else
            {
                for (int i = idx; i < N; i++)
                {
                    s += $"{nums[i]} ";
                    BT(i, cnt + 1, s);
                    s = s.Remove(s.Length - nums[i].ToString().Length - 1);
                }
            }
        }
    }
}