백트래킹DFS
다시푸는 코딩 테스트 준비 일지
응시 사이트 : BOJ
문제 : 15663.N과 M(10)
사용언어 : C#
난이도 : Middle
풀이시간 : 44m
유형 : 백트래킹 , DFS
문제
N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
N개의 자연수 중에서 M개를 고른 수열
고른 수열은 비내림차순이어야 한다.
길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.
입력
첫째 줄에 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 9
9 9
예제 입력 3 복사
4 4
1 1 2 2
예제 출력 3 복사
1 1 2 2
문제 풀이 접근
이 문제에서는 같은 배열의 다른 위치(인덱스)에 같은 값의 숫자가 들어와서, 조금 까다로웠다.
이전 입력 값을 비교해서 비 내림차순으로 필터링 할수 없는 경우여서 값을 넣는건 불가능 했다.
이 문제의 경우는, 배열을 나보다 큰 값을 출력하기 때문에, 값을 하나씩 밀어나가면서 출력하는 방법을 사용해서 출력했다.
중복 출력은 사용하던대로, HashSet을 사용하여 최적화했다.
작성 코드 (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/15664
// * Time : 44m
// */
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[] _visit;
public StringBuilder _sb;
public HashSet<string> _hs;
public void solve()
{
_hs = new HashSet<string>();
string[] _input = Console.ReadLine().Split(' ');
_n = int.Parse(_input[0]);
_m = int.Parse(_input[1]);
_input = Console.ReadLine().Split(' ');
_visit = new bool[_max];
_sb = 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,0);
Console.Write(_sb.ToString());
}
public void BT(int pos, ref int[] _c, int depth)
{
if (pos == _m)
{
string _s = string.Empty;
for (int i = 0; i < pos; ++i)
{
_s += _c[i];
if (i != pos - 1)
_s += ' ';
}
if (_hs.Contains(_s) == false)
{
_hs.Add(_s);
_sb.AppendLine(_s);
}
}
else if (depth == _arr.Length) return;
else
{
_c[pos] = _arr[depth];
BT(pos + 1, ref _c, depth + 1);
BT(pos, ref _c, depth + 1);
}
}
}
}