다시푸는 코딩 테스트 준비 일지
응시 사이트 : BOJ
문제 : 15656.N과 M(7)
사용언어 : C#
난이도 : Middle
풀이시간 : 1h over
유형 : 백트래킹 , DFS
문제
N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.
N개의 자연수 중에서 M개를 고른 수열
같은 수를 여러 번 골라도 된다.
입력
첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7)
둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
예제 입력 1 복사
3 1
4 5 2
예제 출력 1 복사
2
4
5
예제 입력 2 복사
4 2
9 8 7 1
예제 출력 2 복사
1 1
1 7
1 8
1 9
7 1
7 7
7 8
7 9
8 1
8 7
8 8
8 9
9 1
9 7
9 8
9 9예제 입력 3 복사
3 3
1231 1232 1233
예제 출력 3 복사
1231 1231 1231
1231 1231 1232
1231 1231 1233
1231 1232 1231
1231 1232 1232
1231 1232 1233
1231 1233 1231
1231 1233 1232
1231 1233 1233
1232 1231 1231
1232 1231 1232
1232 1231 1233
1232 1232 1231
1232 1232 1232
1232 1232 1233
1232 1233 1231
1232 1233 1232
1232 1233 1233
1233 1231 1231
1233 1231 1232
1233 1231 1233
1233 1232 1231
1233 1232 1232
1233 1232 1233
1233 1233 1231
1233 1233 1232
1233 1233 1233문제 풀이 접근
이 문제는 나 자신을 골라도 되는 조건을 가진 N과 M 시리즈 문제다.
나 자신을 회피하기 위한 _isVisit 변수를 안쓰고 내 조합 배열 내 현재 위치 인덱스에 주어진 배열의 값을 넣어주고 출력해주면 된다.
문제에서 조건이 "중복되는 수열을 여러번 출력하면 안된다" 라는 조건을 해결하기 위해 탐색에 O(1)의 시간복잡도를 사용하는 HashSet을 사용하여 필터링을 해주었다.
수열은 오름차순으로 구성하여 N 중에 M의 조합을 뽑는 방식으로 작성했다.
작성 코드 (C#) - 실패
using System;
using System.Collections.Generic;
using System.Globalization;
using System.Linq;
using System.Text;
/////*
//// * Difficulty :
//// * URL : https://www.acmicpc.net/problem/15656
//// * Time :
//// */
///
namespace Test
{
internal class Program
{
static void Main(string[] args)
{
Solution solution = new Solution();
solution.solve();
}
}
public class Solution
{
public const int _max = 8;
public int _n;
public int _m;
public int[] _arr;
public int[] _per;
public HashSet<string> _ret;
public StringBuilder _sb;
public StringBuilder _compareSb;
public void solve()
{
_ret = new HashSet<string>();
_sb = new StringBuilder();
_compareSb = new StringBuilder();
string[] _in = Console.ReadLine().Split(' ');
_n = int.Parse(_in[0].ToString());
_m = int.Parse(_in[1].ToString());
_in = Console.ReadLine().Split(' ');
_arr = new int[_n];
for (int i = 0; i < _in.Length; ++i)
_arr[i] = Int32.Parse(_in[i]);
List<int> _tempInt = new List<int>(_arr);
_tempInt.Sort(Sorted);
_arr = _tempInt.ToArray();
_per = new int[_m];
BT(0, ref _per, 0, 0, "");
Console.Write(_sb.ToString());
}
public int Sorted(int n, int m)
{
return n.CompareTo(m);
}
public void BT(int pos, ref int[] c, int cnt , int depth, string _s)
{
if (cnt >= _m)
{
_s = _s.Remove(0, 1);
if (_ret.Contains(_s) == false)
{
_ret.Add(_s);
_sb.Append(_s);
_sb.AppendLine();
}
}
else if (pos == _arr.Length) return;
else
{
for(int i = 0; i < _arr.Length;++i)
{
c[pos] = _arr[i];
BT(pos+1, ref c, cnt + 1, depth + 1, _s + $" {_arr[i]}");
}
}
}
}
}
작성 코드 (C#) - 성공
using System;
using System.Collections.Generic;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Text;
/////*
//// * Difficulty :
//// * URL : https://www.acmicpc.net/problem/15656
//// * Time :
///
/// BOJ_15656_N과 M (7)
//// */
///
namespace CodingTestProj
{
internal class Program
{
static void Main(string[] args)
{
Solution solution = new Solution();
solution.solve();
}
}
public class Solution
{
public const int _max = 7;
public int _n;
public int _m;
public int[] _arr;
public int[] _per;
public StringBuilder _sb;
/*
*
*
*
3 1
4 5 2
*
4 2
9 8 7 1
*
*/
public void solve()
{
_sb = new StringBuilder(1000000000);
string[] _in = Console.ReadLine().Split(' ');
_n = int.Parse(_in[0].ToString());
_m = int.Parse(_in[1].ToString());
_in = Console.ReadLine().Split(' ');
_arr = new int[_n];
for (int i = 0; i < _in.Length; ++i)
_arr[i] = Int32.Parse(_in[i]);
List<int> _tempInt = new List<int>(_arr);
_tempInt.Sort();
_arr = _tempInt.ToArray();
_per = new int[_m];
BT(0, ref _per, 0, 0);
using (StreamWriter writer = new StreamWriter(Console.OpenStandardOutput()))
{
writer.AutoFlush = true;
Console.SetOut(writer); // Console.Out을 StreamWriter로 대체
// 이제 Console.WriteLine은 StreamWriter를 통해 콘솔에 출력
Console.Write(_sb.ToString());
}
}
public int Sorted(int n, int m)
{
return n.CompareTo(m);
}
public void BT(int pos, ref int[] c, int cnt, int depth)
{
if (cnt >= _m)
{
for (int i = 0; i < cnt; ++i)
{
_sb.Append(c[i]);
if (i != cnt - 1)
_sb.Append(" ");
}
_sb.AppendLine();
}
else if (pos == _arr.Length) return;
else
{
for (int i = 0; i < _arr.Length; ++i)
{
c[pos] = _arr[i];
BT(pos + 1, ref c, cnt + 1, depth + 1);
}
}
}
}
}
해결 방향성
해결 방향성은 2가지 였다.
1.StringBuilder에 넣을 문자의 크기가 총합적으로 크다고 판단될 경우 초기에 많은 영역을 할당.
2.Console출력은 느리니, StreamWriter로 콘솔 출력 매체를 변경하여 출력할 것.
1번의 경우, StringBuilder의 내부 동작 로직 때문에, 초기에 큰 메모리를 할당해놓으면 시간적인 효율을 얻을 수 있다.
그 이유는 StringBuilder의 메모리는 동적 배열처럼 할당되기 때문이다.
쉽게 C++에서 Vector 의 할당 정책만 보아도, Vector는 초기 동적 배열을 원하는 만큼 선 할당할 수 있다. Reserve() 였던것 같다. 그 후 배열에 추가될 때, 기억은 잘 안나지만 현재 배열 크기 + 전체 배열 크기 * 0.5 정도였던거 같은데, 통상적으로 1.5배라고 생각하면 된다.
정확한 식은 알고있었는데 까먹은 것 같다.
아무튼 StringBuilder도 처음에 10개 Char[] 을 할당했는데, 넘어가는 경우 10개의 char를 모두 복사하고 자리가 남는 메모리영역에 추가로 할당한다.
이러한 연산이 수열뽑히는 타이밍 내내 있었으니, 느려질 법도 하고, 초기에 넉넉하게 선언하는 것이 합리적으로도 보인다.
2번의 경우는, 정확하게 이해는 안된다. Console 출력은 StreamWriter 보다 결과적으로 느렸다. 라는 것이 결과로써 알 수 있었지만, 단순 Console로는 풀 수 없었다.
그렇다면 이 문제는 C# 언어의 경우 StreamWriter를 알아야만 풀 수 있는 문제인지가 조금 의문스럽다.
코드 결과
** 이 문제를 해결함으로써, 실버 2가 되었다. (24.11.28)