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

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

• 응시 사이트 : BOJ

• 문제 : 15651.N과 M(3)

• 사용언어 : C#

• 난이도 : Easy ~ Middle

• 풀이시간 : 16m

• 유형 : 백트래킹 , DFS

문제

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

• 1부터 N까지 자연수 중에서 M개를 고른 수열

• 같은 수를 여러 번 골라도 된다.

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7)

출력

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

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

예제 입력 1 복사

3 1

예제 출력 1 복사

1
2
3

예제 입력 2 복사

4 2

예제 출력 2 복사

1 1
1 2
1 3
1 4
2 1
2 2
2 3
2 4
3 1
3 2
3 3
3 4
4 1
4 2
4 3
4 4

예제 입력 3 복사

3 3

예제 출력 3 복사

1 1 1
1 1 2
1 1 3
1 2 1
1 2 2
1 2 3
1 3 1
1 3 2
1 3 3
2 1 1
2 1 2
2 1 3
2 2 1
2 2 2
2 2 3
2 3 1
2 3 2
2 3 3
3 1 1
3 1 2
3 1 3
3 2 1
3 2 2
3 2 3
3 3 1
3 3 2
3 3 3

문제 풀이 접근

이 문제는 N과 M(2) 시리즈에서 단순히 선택했던 번호를 중복을 허가하여 중복에 대한 필터링을 제거한 문제다.

풀이법은 N과 M(2) 코드에서 중복을 체크하는 Visited 변수를 삭제한 후 제출을 하였다.
이 N과 M 시리즈 문제를 풀면서 문제 케이스는 확실하게 맞고 들어갔지만, 제출케이스에서 시간 초과 오류가 나는 경우를 몇번 보았다. N과 M(1) 도 시간 초과때문에 풀지 못한 케이스 중 하나다.
그래서 이 부분에 대해서는 조금 찾아보았는데, Console.WriteLine을 순열을 찾은 매번 케이스마다 출력하게 되면 시간 초과가 나는 경우가 더러 있는 것으로 보인다.

문제의 정답을 좌우할 만큼 시간초과가 날줄은 몰랐는데 StringBuilder의 AppendLine으로 텍스트들을 쌓고 한번에 출력하는 방식으로 하여 문제를 해결할 수 있다.

작성 코드 (C#)

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

///*
// * Difficulty : Easy
// * URL : https://www.acmicpc.net/problem/15651
//  * Time : 16m
// */

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[] _per;
        public int[] _arr;

        public int _curPos;

        public StringBuilder _sb;

        public void solve()
        {
            string[] _input = Console.ReadLine().Split(' ');
            _n = int.Parse(_input[0]);
            _m = int.Parse(_input[1]);
            _sb= new StringBuilder();

            _arr = new int[_max];
            _per = new int[_max];

            for (int i = 0; i < _max; ++i)
                _arr[i] = i + 1;

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

        public void dfs(int cnt)
        {
            if(cnt >= _m)
            {
                for(int i  = 0; i < cnt; ++i)
                {
                    _sb.Append(_per[i]);

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

                _sb.AppendLine();
            }
            else
            {
                for(int i = 0; i < _n; ++i)
                {
                    _per[cnt] = _arr[i];
                    dfs(cnt + 1);
                }
            }
        }
    }
}

코드 결과