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

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

• 응시 사이트 : BOJ

• 문제 : 15666.N과 M(12)

• 사용언어 : C#

• 난이도 : Easy

• 풀이시간 : 11m

• 유형 : 백트래킹

문제

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

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

• 고른 수열은 오름차순이어야 한다.

입력

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

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

출력

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

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

예제 입력 1 복사

3 1
4 5 2

예제 출력 1 복사

2
4
5

예제 입력 2 복사

4 2
9 8 7 1

예제 출력 2 복사

1 7
1 8
1 9
7 8
7 9
8 9

예제 입력 3 복사

4 4
1231 1232 1233 1234

예제 출력 3 복사

1231 1232 1233 1234

문제 풀이 접근

풀려있지 않은 문제여서 모든 N과 M 시리즈를 풀이한 다음 다시 풀었다.
크게 어려운건 없고, 오름차순, 중복 순열에 대한 필터만 해주면 쉽게 풀린다.

문제가 원래 이런진 모르겠으나, 다른 시리즈에서 잘 써먹는 비내림차순이라고 했으면 좀 더 이해하기 쉬웠을 것 같다.

다른 문제와 동일하게 출력 부분 최적화를 위해선 StringBuilder를 이용해서 한번에 출력 메시징 처리를 하였고, HashSet을 이용해 중복탐색에 대한 시간을 최소화 하였다.

작성 코드 (C#)

using System;
using System.Collections.Generic;
using System.Text;

/////*
//// * Difficulty : Easy
//// * URL : https://www.acmicpc.net/problem/15655
////  * Time : 11m 
//// */
///
namespace CodingTestProj
{
    internal class Program
    {
        static void Main(string[] args)
        {
            Solution solution = new Solution();
            solution.solve();
        }
    }

    public class Solution
    {
        public const int _max = 9;
        public const int _valmax = 10001;
        public int _n;
        public int _m;
        public int[] _arr;
        public int[] _per;

        public bool[] _isVisit;

        public HashSet<string> _hs;

        public StringBuilder _sb;
        public void solve()
        {
            _sb = new StringBuilder();
            _hs = new HashSet<string>();

            string[] _input = Console.ReadLine().Split(' ');
            _n = int.Parse(_input[0]);
            _m = int.Parse(_input[1]);

            _input = Console.ReadLine().Split(' ');

            _arr = new int[_n];
            _per = new int[_m];

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

            Array.Sort(_arr);

            BT(0, ref _per, -1);

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

        public void BT(int _cnt, ref int[] _c, int _prev)
        {
            if(_cnt == _m)
            {
                string _in = string.Empty;

                for(int i = 0; i < _cnt; ++i)
                {
                    _in += _c[i];

                    if (i != _cnt - 1)
                        _in += ' ';
                }

                if (_hs.Contains(_in) == false)
                {
                    _hs.Add(_in);
                    _sb.Append(_in);
                    _sb.AppendLine();
                }
            }
            else
            {
                for(int i = _cnt; i < _n; ++i)
                {
                    if (_prev >= _arr[i]) continue;

                    _c[_cnt] = _arr[i];
                    BT(_cnt + 1, ref _c, _arr[i]);
                }
            }
        }
    }
}

코드 결과