다시푸는 코딩 테스트 준비 일지
응시 사이트 : BOJ
문제 : 15666.N과 M(12)
사용언어 : C#
난이도 : Middle
풀이시간 : 5m 54
유형 : 백트래킹
문제
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 1
1 7
1 9
7 7
7 9
9 9
예제 입력 3 복사
4 4
1 1 2 2
예제 출력 3 복사
1 1 1 1
1 1 1 2
1 1 2 2
1 2 2 2
2 2 2 2
문제 풀이 접근
이 문제를 보고나서, 이전에 적용했었던 이전 값에 대한 논리, 탐색하는 로직이 바로 떠올라서 적용했더니, 바로 풀 수 있었다.
이 문제에서 요구하는 요구사항은
1) 자신을 다시 골라도 됌
2) A0 <= A1 .... <= Ak 까지 문제에서 정의하길 "비 내림차순" 순열만 통과 가능하다.
이 부분에 대한 설명은 링크의 문제 풀이 접근에서 더 자세히 확인할 수 있다.
크게 설명할 로직이 없어서 N의 M시리즈 문제는 이렇게 마지막일 것 같다.
다이아몬드에 있긴하지만, 나중에 실력을 끌어올린다면 도전해보겠다. 그걸 제외하면 할 수 있는 실력 범위내에선 모두 풀었다.
작성 코드 (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/15666
// * Time : 5m 54s
// */
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[] _c = new int[_m];
for (int i = 0; i < _arr.Length; ++i)
_arr[i] = int.Parse(_input[i]);
Array.Sort(_arr);
BT(0, ref _c, -1);
Console.Write(_sb.ToString());
}
public void BT(int pos, ref int[] _c, int _Prev)
{
if(pos == _m)
{
string _s = string.Empty;
for(int i = 0; i < _c.Length; ++i)
{
_s += _c[i];
if (i != _c.Length - 1)
_s += ' ';
}
if(!_hs.Contains(_s))
{
_hs.Add(_s);
_sb.Append(_s);
_sb.AppendLine();
}
}
else
{
for(int i =0; i< _n; ++i)
{
if (_arr[i] < _Prev) continue;
_c[pos] = _arr[i];
BT(pos + 1, ref _c, _arr[i]);
}
}
}
}
}코드 결과
