코딩테스트 준비 - N과 M(9)

다시푸는 코딩 테스트 준비 일지

• 응시 사이트 : BOJ

• 문제 : 15663.N과 M(9)

• 사용언어 : C#

• 난이도 : Middle

• 풀이시간 : 38m

• 유형 : 백트래킹 , DFS

문제

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

• N개의 자연수 중에서 M개를 고른 수열

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

예제 입력 1 복사

3 1
4 4 2

예제 출력 1 복사

2
4

예제 입력 2 복사

4 2
9 7 9 1

예제 출력 2 복사

1 7
1 9
7 1
7 9
9 1
9 7
9 9

예제 입력 3 복사

4 4
1 1 1 1

예제 출력 3 복사

1 1 1 1

문제 풀이 접근

이 문제부터는 N과M 시리즈에서 배열의 값도 동일한 숫자도 나오는 것 같다.
동일한 수를 배열에 들어갈 수도 있게 함으로써, 중복 순열에 대한 처리 등을 어떻게 하는지 체크하는 것으로 보인다.

만약 List와 같은 탐색에 O(N) 시간 복잡도를 가진다면, 아마도 이 문제에선 결과를 타임 아웃으로 리턴할 것으로 보인다.

문제는 크게 어려운 것은 없으며, HashSet을 이용해, 이미 HashSet이 담겨진 내용은 StringBuilder에 입력되지 않도록 처리하여 중복 출력을 회피하였다.

작성 코드 (C#)

using System;
using System.Collections;
using System.Collections.Generic;
using System.Xml.Linq;
using static CodingTestProj.Program;
using System.Text;

///*
// * Difficulty : Middle
// * URL : https://www.acmicpc.net/problem/15663
//  * Time : 38m
// */

namespace CodingTestProj
{
    internal class Program
    {
        static void Main(string[] args)
        {
            Solution solu = new Solution();
            solu.solve();
        }
    }

    public class Solution
    {
        public const int _max = 8;
        public int _n;
        public int _m;
        public int[] _arr;
        public bool[] _isVisited;


        public StringBuilder _sb;
        public StringBuilder _sbc;

        public HashSet<string> _hs;
        public void solve()
        {
            _hs = new HashSet<string>();
            string[] _input = Console.ReadLine().Split(' ');
            _isVisited = new bool[_max];

            _n = int.Parse(_input[0]);
            _m = int.Parse(_input[1]);
            _input = Console.ReadLine().Split(' ');
            _sb = new StringBuilder();
            _sbc = new StringBuilder();
            _arr = new int[_n];
            int[] _per = new int[_m];

            for (int i = 0; i < _arr.Length; ++i)
                _arr[i] = int.Parse(_input[i]);

            Array.Sort(_arr);

            BT(0, ref _per);
            Console.Write(_sb.ToString());
        }

        public void BT(int cnt, ref int[] _c)
        {
            if (cnt == _m)
            {
                _sbc.Clear();

                for (int i = 0; i < cnt; ++i)
                {
                    _sbc.Append(_c[i]);

                    if (i != cnt - 1)
                        _sbc.Append(' ');
                }

                if(_hs.Contains(_sbc.ToString()) == false)
                {
                    _hs.Add(_sbc.ToString());
                    _sb.Append(_sbc.ToString());
                    _sb.AppendLine();
                }
            }
            else
            {
                for (int i = 0; i < _n; ++i)
                {
                    if (_isVisited[i] == false)
                    {
                        _c[cnt] = _arr[i];
                        _isVisited[i] = true;
                        BT(cnt + 1, ref _c);
                        _isVisited[i] = false;
                    }
                }
            }
        }
    }
}

코드 결과

** 실버 2까지 앞으로 2점 남았다.