다시푸는 코딩 테스트 준비 일지
응시 사이트 : BOJ
문제 : 15654.N과 M(5)
사용언어 : C#
난이도 : Middle
풀이시간 : 1h over
유형 : 백트래킹 , DFS
문제
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 1
7 8
7 9
8 1
8 7
8 9
9 1
9 7
9 8
예제 입력 3 복사
4 4
1231 1232 1233 1234
예제 출력 3 복사
1231 1232 1233 1234
1231 1232 1234 1233
1231 1233 1232 1234
1231 1233 1234 1232
1231 1234 1232 1233
1231 1234 1233 1232
1232 1231 1233 1234
1232 1231 1234 1233
1232 1233 1231 1234
1232 1233 1234 1231
1232 1234 1231 1233
1232 1234 1233 1231
1233 1231 1232 1234
1233 1231 1234 1232
1233 1232 1231 1234
1233 1232 1234 1231
1233 1234 1231 1232
1233 1234 1232 1231
1234 1231 1232 1233
1234 1231 1233 1232
1234 1232 1231 1233
1234 1232 1233 1231
1234 1233 1231 1232
1234 1233 1232 1231문제 풀이 접근
이 문제는, N과 M시리즈에서 조건이 추가된 문제인데, 길게 설명할 것도 없기도 하고, 플로우는 아래와 같다.
1. 처음에 주어진 배열을 정렬한다.
2. 나 자신을 제외하여 0부터 순회하면서 순열을 찾는다.
3. 출력한다.
여기서 추가된 조건은 " 수열은 사전 순으로 증가하는 순서로 출력해야 한다. " 이다.
이 조건에 대해서 나는 살짝 의문이다.
" 수열은 사전 순으로 증가하는 순서로 출력해야 한다. " 라는 것을 나는 문자열의 사전 순으로 생각해서, string으로 받아서 문자열의 사전 순서로 오름차순하여 배열을 구성했고, 그렇게 순열을 만들었는데, 실패했었다.
반례 케이스도 문제에선 없었고, 일부 사용자들이 반례를 올려놓은 것을 보고 문자열의 사전순이 아닌 정수의 사전순으로 바꿨더니 해결할 수 있었다.
여기서 정수와 문자열의 사전순 정렬의 차이는 이렇다.
[1 , 2 , 11 , 3 , 4 , 5 , 10] 이 있다고 할때 결과는 아래와 같다.
- 숫자의 사전순 정렬 : [1,2,3,4,5,10,11]
- 문자열의 사전순 정렬 : [1,10,11,2,3,4,5]
이 이유는 숫자는 그 문자의 사전순 크기를 비교하여 정렬하지만, 문자열은 다음 문자의 크기를 기준으로 사전순 정렬한다. 즉 10일 때, 1을 사전순 정렬하고, 그 다음 문자인 0을 가져와서 정렬한다.
이렇기 때문에 둘의 결과는 다르고, 내가 풀이했던 방식은 오답이 나왔다.
고로 이 문제의 표기에 대해서 풀면서도, 지금 포스팅을 진행하면서도 바뀌어야 하지 않나 라는 의견이긴 하다.
작성 코드 (C#)
using System;
using System.Collections.Generic;
using System.Text;
/////*
//// * Difficulty : Easy
//// * URL : https://www.acmicpc.net/problem/15654
//// * Time : 1h over
//// */
///
namespace Test
{
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> _ret;
public void solve()
{
_ret = new HashSet<string>();
string[] _in = Console.ReadLine().Split(' ');
_n = int.Parse(_in[0].ToString());
_m = int.Parse(_in[1].ToString());
_isVisit = new bool[_valmax];
_in = Console.ReadLine().Split(' ');
_arr = new int[_max];
for (int i = 0; i < _in.Length; ++i)
_arr[i] = Int32.Parse(_in[i]);
_per = new int[_m];
List<int> _temp = new List<int>(_arr);
_temp.Sort(Sorted);
_arr = _temp.ToArray();
BT(ref _arr, ref _per, 0, 0);
int index = 0;
foreach (string s in _ret)
{
Console.Write(s);
if (index != _ret.Count - 1)
Console.WriteLine();
}
}
public int Sorted(string _item1, string _item2)
{
bool _isEmptyitem1 = _item1 == null || _item1.Length == 0 ? true : false;
bool _isEmptyitem2 = _item2 == null || _item2.Length == 0 ? true : false;
if (_item1 == null)
_item1 = " ";
if (_item2 == null)
_item2 = " ";
if (_isEmptyitem1 != _isEmptyitem2)
return _isEmptyitem1.CompareTo(_isEmptyitem2);
return _item1.CompareTo(_item2);
}
public int Sorted(int _item1, int _item2)
{
bool _isEmptyitem1 = _item1 == 0 ? true : false;
bool _isEmptyitem2 = _item2 == 0 ? true : false;
if (_isEmptyitem1 != _isEmptyitem2)
return _isEmptyitem1.CompareTo(_isEmptyitem2);
return _item1.CompareTo(_item2);
}
public void BT(ref int[] _arr, ref int[] _per, int _cnt, int _pos)
{
if (_cnt >= _m)
{
string _st = string.Empty;
for (int i = 0; i < _cnt; ++i)
{
_st += _per[i];
if (i != _cnt - 1)
_st += " ";
}
if (_ret.Contains(_st) == false)
_ret.Add(_st);
}
else
{
for (int i = 0; i < _n; ++i)
{
if (_isVisit[Int32.Parse(_arr[i].ToString())] == false)
{
_isVisit[Int32.Parse(_arr[i].ToString())] = true;
_per[_pos] = _arr[i];
BT(ref _arr, ref _per, _cnt + 1, _pos + 1);
_isVisit[Int32.Parse(_arr[i].ToString())] = false;
}
}
}
}
}
}
코드 결과
